引言

在前面的教程中，我们学习了函数与控制结构（循环）。那么在这一章，我们将学习一个全新的，但又与函数息息相关的概念：递归。

在算法问题中，递归是一个非常重要的思想，也是一个强有力的工具😎😎

什么是递归？

定义： 递归是一种函数调用自身来解决问题的方法，是一种针对使用简单的循环难以编程实现的问题，提供优雅解决方案的技术。

是不是有点抽象？🤣 没关系，让我们来举个简单的例子~

我们在高中学习排列组合、概率统计的时候，常常会遇到计算阶乘（factorial）的情况。例如，计算 $10!$ 的值。

对于刚刚学过循环的你，是不是首先会考虑用循环来解决？😊

是的，使用循环是【最直观】的方式：

symmetry = 1
for i in range(1, 11):
    symmetry *= i

print("The factorial of 10 is", symmetry)

输出结果为：

The factorial of 10 is 3628800

但是既然都学到递归了，我们不妨用一种新的思路来解决计算阶乘的问题。

递归是一种分治（divide and conquer）思想，将一个大问题分解成更小、更易解决的问题。

回归到计算阶乘这个问题本身，对于求 $n!$ ，无非就是 $n * (n - 1) * (n - 2) * ... * 2 * 1$ ；用递归来看的话：

大问题： 计算 $n!$
分解： 计算 $n * (n - 1)!$
更小的问题： 不断计算 $(n - 1)!, (n - 2)!$ ，直到计算到 $1!$ ，此时我们知道 $1!$ 是已知的，称为基础情况（base case）或终止条件（stopping condition）

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n - 1)

ans = factorial(10)
print("The factorial of 10 is: ", ans)

输出结果同上：

The factorial of 10 is 3628800

再说得详细一点，使用递归定义的函数是一种【自我调用】的函数。

例如 $10! = 10 * 9! = 10 * 9 * 8! = 10 * 9 * 8 * 7! = 10 * 9 * 8 * 7 * 6!$ ... $10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1!$
根据前面定义的函数来表示的话，就是 factorial(10) = 10 * factorial(9) = 10 * 9 * factorial(8) = ... = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * factorial(1) 、

由此我们可以看出，这个函数是从 factorial(10) 开始，层层深入，一直自我调用，直到 factorial(1) 遇到终止条件而结束。这，就是递归。

注意： 在递归中，base case 是非常重要的，如果在使用递归定义函数时没有写明 base case，那么函数将无限自我调用，就会出现 stackOverFlow 错误。

Tips： 如果实在觉得难以理解，可以参照这个函数的流程，一步一步用笔在纸上把每一步的流程都写出来，有助于你的理解！🤗

经典问题

除了计算阶乘以外，斐波那契数列、汉诺塔问题等也是递归中的经典问题

斐波那契数列求和在解决这个经典的问题之前，我们有必要知道斐波那契数列的计算方式：
$F(0) = 0$
$F(1) = 1$
$F(n) = F(n - 1) + F(n - 2)$ （对于n >= 2）

在明确了斐波那契数列的计算方式之后，我们可以很容易地发现，斐波那契数列是基于递归思想的。这里的 base case 即为当 n == 1 时 return 1 ，当 n == 0 时 return 0 。由此，我们可以写出如下代码：

def fibonacci(n):
    if n <= 1:  #这里可以将0和1的两种情况简化为这一种
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

print("The value of the 10th term in the Fibonacci sequence is: ", fibonacci(10))

输出结果为：

The value of the 10th term in the Fibonacci sequence is:  55

汉诺塔问题汉诺塔是一个非常经典的问题，也是很多编程教材的入门例题。对于编程初学者而言，这个问题会很抽象，所以建议结合视频学习！🥰

问题描述：

有三根杆子，编号分别为A、B、C。
在杆子A上有n个圆盘，圆盘大小各不相同，并按照从大到小的顺序叠放，最小的在最上面。
目标是将所有圆盘从杆子A移动到杆子C，并保持圆盘的顺序。

规则：

每次只能移动一个圆盘。
圆盘可以放在任意一根杆子上。
圆盘不能放在比它小的圆盘上面。

递归实现： base case：如果只有一个圆盘，则直接将其从杆子A移动到杆子C

递归情况：

调用自身将n-1个圆盘从杆子A移动到杆子B。
将第n个圆盘从杆子A移动到杆子C。
调用自身将n-1个圆盘从杆子B移动到杆子C。

代码实现如下：

def hanoi(n, a, b, c):
    if n == 1:
        print(a, '-->', c)
    else:
        hanoi(n-1, a, c, b)
        print(a, '-->', c)
        hanoi(n-1, b, a, c)

hanoi(3, 'A', 'B', 'C')

输出结果为：

A --> C
A --> B
C --> B
A --> C
B --> A
B --> C
A --> C

递归 VS 循环

学到这里，相信你们对递归已经有了新的理解，让我们来总结一下递归与循环的优劣吧😉

递归和循环是两种常见的编程技术，用于重复执行一系列操作。它们各有优缺点，适用于不同的场景。以下是它们的对比：

递归：

优点：

代码简洁： 递归通常能使代码更简洁、直观，尤其是解决分治问题或自然递归的问题（如树和图的遍历、斐波那契数列、阶乘等）。
易于理解： 对于一些问题，递归能更自然地表达解决问题的思路，比如在处理具有递归性质的数据结构时。
减少代码量： 递归可以避免使用额外的数据结构（如栈或队列）来管理复杂的状态变化。

缺点：

性能问题： 递归调用每次都会增加栈的深度，可能导致栈溢出（stackOverFlow），尤其是在递归层数很深的时候。
效率较低： 递归通常有【较高】的时间和空间开销，因为每次递归调用都会增加函数调用栈。
难以调试： 递归代码有时较难调试和理解调用顺序，特别是涉及多个递归调用时。

循环：

优点：

性能较好： 循环通常比递归占用更少的内存，因为它不需要函数调用栈。
避免栈溢出： 由于循环不依赖调用栈的深度，所以适合处理大量迭代而不会导致栈溢出。
易于优化： 循环结构通常更容易进行性能优化，特别是在编译器层面。

缺点：

代码复杂： 对于某些递归问题，使用循环实现可能会使代码变得复杂且难以理解。
不直观： 在处理具有自然递归特性的问题时，循环的解决方案可能不如递归直观。
状态管理： 循环有时需要显式地管理多个状态变量，这可能导致代码不够清晰。

如何选择

递归适用于自然递归的问题，比如树和图的遍历、快速排序、归并排序等。
循环更适合简单的迭代任务，如遍历数组或列表。

Labs

使用递归完成二分查找的实现
使用递归完成选择排序