python递归基础

学习递归前，需先理解函数的工作机制，递归概念适用于所有编程语言。

什么是递归？ 多数编程语言中，函数可调用其他函数，而递归是函数调用自身的技术。

例：

def   call_me():    

   call_me() 

这里函数自我调用，即递归。 但“自我调用”只是递归的程序定义。递归的核心是将问题分解为更小部分，直至无法再分，通过解决小问题并组合结果来解决整个问题。

用生活例子类比递归 想象你在上海迪士尼乐园排队，想知道队伍总人数。你可以问前面的人：“你前面有多少人？” 对方若也不知道，会用同样的方式问更前面的人，直到有人前面没人（即第一个人），他会回答“0”。接着后面的人依次加1回复，最后你就能知道总人数——这就是递归的思路：通过层层拆解问题，从最基础的情况（终止条件）反向推导答案。

Image

队伍中的每个人代表同一问题的一个较小实例：确定前面的人数。通过解决这些较小的实例并结合它们的结果，整个问题得到了解决。这正是递归的工作原理。

递归的简单例子

计算阶乘是递归的最简单例子，它将真正帮助你理解其工作原理。

有很多方法可以计算一个数的阶乘。但在这里，我们将看到递归的方式来找到它。

在思考我们如何做到这一点之前，我们需要知道一个数的阶乘是什么。

一个数的阶乘是从 1 到该数的所有数字的乘积。

例如，5 的阶乘是 120 —— 即 5×4×3×2×1。

我们还可以用数学方式表示如下：

5×(5−1)!

这意味着如果我们知道 (5−1)! 的值，我们就可以通过简单地将 5 乘以它来轻松得到阶乘。

这就是我们如何找到 4、3、2、1 和 0 的阶乘：

Factorial of 4 = 4×(4−1)!
Factorial of 3 = 3×(3−1)!
Factorial of 2 = 2×(2−1)!
Factorial of 1 = 1
Factorial of 0 = 1

通过观察这些，很明显要找到 5 的阶乘，我们必须将 5 乘以 4!。

更普遍的例子

要找到 n 的阶乘，我们需要将 n 乘以 (n−1)!。这就是你需要递归执行的过程。

现在，必须为递归设置一个停止条件。停止条件是我们不再执行其他操作的地方。当 n 是 1 或 0 时，我们可以简单地停止递归，因为这些值的阶乘是已知的。我们可以简单地说 1 的阶乘是 1，对于 0 也是如此。

因此，分解下来，要找到 n 的阶乘，所需做的最小工作量是 n×(n−1)!。当我们找到 1 或 0 的阶乘时，我们可以停止对它进行操作。

让我们看看代码是怎样的：

# 计算 n 的阶乘
def fact(n):
      # 最少工作量
     return n * fact(n - 1)

n = 5

# 计算阶乘
factorial = fact(n)
print(factorial)

输出:

120

让我们看看它是如何工作的：

在第一次函数调用中，计算了 5 的阶乘。接着在第二次调用中，计算了 4 的阶乘，以此类推，直到计算 2 的阶乘。

图像

递归计算 5 的阶乘

在调用 2 的阶乘时，我们有2×fact(2−1)，即2×fact(1)。

这达到了我们的基本条件。因此，递归停止，2×fact(1)返回2×1给前一个函数调用，并且结果从堆栈中弹出。

图像

第四次函数调用返回 2 给前一个函数调用并从堆栈中弹出

类似地，这里是其他内容的计算方式：

图像

第三次函数调用返回 6 给前一个函数调用并从堆栈中弹出

图像

第二次函数调用返回 24 给前一个函数调用并从堆栈中弹出

图像

第一次函数调用返回 120 给初始函数调用并从堆栈中弹出

所以函数最终将值 120 返回给初始函数调用。

总结

这只是递归的入门介绍