​ 递归是个很神奇的思想，与迭代不同的地方在于，迭代通过原来的变量推出新值，接着以新值为初始值继续递推，直到满足条件，而递归则是A循环调用本身。举个简单的例子，计算1到n的和：

​ 迭代实现：

1
2
3
4
5
def a(n):
    sum = 0
    for i in range(1, n + 1):
        sum += i
    return sum

​ 每次都以sum的新值为基础,以sum+=i这个式子递推，直到实现功能。

​ 递归实现：

1
2
3
4
def b(n):
    if n == 1:
        return 1
    return n + b(n - 1)

​ 重复调用n+b(n-1)操作，直到n==1结束。

​ 从上面的对比我们可以看出，要想写一个递归程序，需要关注两个部分，一个是程序的出口（如果没有会造成死循环），另一个则是调用的函数推导式，上述程序的推导式可写为：n+(n-1)+(n-2)+(n-3)+……+1。

​ 递归的思想比较简单，通俗易懂，难就难在怎么去应用。接下来我们举两个经典的例子。

  • 计算n的阶乘：

    1
    2
    3
    4
    5
    def func(n):
        if n == 1 or n == 2:
            return 1
        else:
            return func(n-1) + func(n-2)

    阶乘在各种算法题目解法的出现频率非常高，例如爬楼梯问题，兔子问题等。

  • 汉诺塔问题

    这里简述一下。有三个立柱，其中一个立柱上按从下往上，从大到小的顺序依次叠放n个中空圆盘，现要求将圆盘转移到另一个立柱上，且顺序依旧为从下往上，从大到小。

    解决方案就是利用第三个立柱进行中转。以两个圆盘为例，先将小圆盘移到三柱，再将大圆盘移到二柱，然后将三柱的小盘移到二柱，转移完成。如果有n个盘该怎么办呢？其实还是上述的操作，直接上代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    def move(n,a,b,c): #a是起始柱，b是辅助柱，c是目标柱
        if n == 1:
            print(a,'->',c)
        else:
            # 将n-1个盘子从a --> b
            move(n-1,a,c,b)
            # 将剩余的最后一个盘子从a --> c
            print(a,'->',c)
            # 将剩余的n-1个盘子从 b --> c
            move(n-1,b,a,c)

​ 要想实现递归，最关键的地方就在于找到出口条件和可重复的操作式，需要大量的练习。