递归¶

分区问题（Partition Problem）¶

正整数 n 的分割数 n 是指 n 可以用 m 以内的正整数各部分之和依次递增的方式来表示。例如，用 4 以内的部分对 6 进行分割（（6，4）分割）的次数是 9。

6 = 2 + 4
6 = 1 + 1 + 4
6 = 3 + 3
6 = 1 + 2 + 3
6 = 1 + 1 + 1 + 3
6 = 2 + 2 + 2
6 = 1 + 1 + 2 + 2
6 = 1 + 1 + 1 + 1 + 2
6 = 1 + 1 + 1 + 1 + 1 + 1

解法： 我们可以递归地将使用最大为 m 的整数分割 n 的问题简化为两个更简单的问题：

假设使用了数字m进行分割：分割一个更小的数 n-m
假设永远不使用数字m进行分割：用最大为 m-1 的更小分量进行分割。

递归出口：被分割数 n 为 0 时，说明找到了一个可行的分割方法，返回 1；当被分割数 n 为负数时，说明当前分割不可行，返回 0；当割刀 m 为 0 时，说明没有可用的割刀，返回 0。

对于上面的例子，求（6，4）分割，我们可以将其分解为（6-4，4）分割和（6，4-1）分割。

def count_partitions(n, m):
        """Count the ways to partition n using parts up to m."""
        if n == 0:
            return 1
        elif n < 0:
            return 0
        elif m == 0:
            return 0
        else:
            return count_partitions(n-m, m) + count_partitions(n, m-1)

汉诺塔问题（Towers of Hanoi）¶

汉诺塔由三根杆子和若干个大小不一的圆盘组成，这些圆盘可以滑动到任意一根杆子上。开始时， n 的圆盘按照由大到小的顺序整齐地堆叠在 start 的杆子上，最小的圆盘在最顶端，形成一个圆锥形。目的是按照以下规则将整堆圆盘移动到 end 杆上：

一次只能移动一个磁盘。
每次移动包括从其中一根杆上取下最上面（最小）的磁盘，然后将其滑到另一根杆上，放在该杆上可能已经存在的其他磁盘之上。
任何磁盘都不得放在较小磁盘的顶部。

解法：

策略：将除底部棋子以外的所有棋子移动到第二根杆子上，然后将底部棋子移动到第三个杆子上，再将第二根杆子的所有棋子从第二根杆子上移动到第三个杆子上。

例如，假设初始6个碟子在1杆(start)，2杆(assistant)、3杆(end)0个碟子。我们要把6个碟子从start杆移动到end杆(6,start = 1,end = 3)。那么问题可以递归地转化为以下三个子问题：

把上面的5个碟子从start杆移动到assistant杆(5,start,end = assistant)，此时assistant杆变成了end杆。
将底部棋子（这个时候是顶层碟子了）移动到第三个杆子上:print("把顶层碟子从", start, "->", end)
把5个碟子从assistant杆移动到end杆(5,start = assistant,end)，此时assistant杆变成了start杆。

递归出口：当只有一个碟子时，直接将碟子从start杆移动到end杆。

def print_move(origin, destination):
    """Print instructions to move a disk."""
    print("Move the top disk from rod", origin, "to rod", destination)

def move_stack(n, start, end):
    if n == 1:
        print_move(start, end)
        return None
    nodiskrod = 6 - start - end
    move_stack(n-1, start, nodiskrod)
    print_move(start, end)
    move_stack(n-1, nodiskrod, end)