企业官网建设流程全解析

Python递归详解：为什么说递归是“先递后归”？（以阶乘为例）

前言

很多初学者学习递归时，都会有一个疑问：

递归到底是怎么执行的？

为什么总说递归是“先递后归”？

今天我们通过最经典的「阶乘」案例，把递归的执行过程彻底讲明白。

什么是递归？

递归（Recursion）就是：

函数自己调用自己。

例如：

deffn(n):returnn*fn(n-1)

这里fn()在函数内部又调用了自己，因此这就是递归。

不过仅仅这样写会无限调用下去，所以递归必须有一个终止条件。

阶乘是什么？

数学中的阶乘表示：

5! = 5 × 4 × 3 × 2 × 1

计算结果：

5! = 120

观察规律：

5! = 5 × 4! 4! = 4 × 3! 3! = 3 × 2! 2! = 2 × 1! 1! = 1 × 0! 0! = 1

于是我们得到递归公式：

f(n) = n * f(n-1)

终止条件：

f(0) = 1

Python实现

deffactorial(n):ifn==0:return1returnn*factorial(n-1)print(factorial(5))

输出：

120

代码虽然只有几行，但执行过程却非常有意思,可以先看看下面这张图有助于理解一下。

第一阶段：递（不断向下调用）

计算：

factorial(5)

首先进入：

factorial(5) = 5 * factorial(4)

发现还不知道factorial(4)的结果。

于是继续调用：

factorial(4) = 4 * factorial(3)

继续：

factorial(3) = 3 * factorial(2)

继续：

factorial(2) = 2 * factorial(1)

继续：

factorial(1) = 1 * factorial(0)

最后：

factorial(0) = 1

此时到达终止条件。

整个向下调用过程如下：

factorial(5) ↓ factorial(4) ↓ factorial(3) ↓ factorial(2) ↓ factorial(1) ↓ factorial(0)

这一阶段就叫：

递

因为程序一直在向下递进调用。

第二阶段：归（逐层返回结果）

当执行到：

factorial(0)=1

以后，开始返回。

首先返回给：

factorial(1) = 1 * factorial(0) = 1 * 1 = 1

接着返回给：

factorial(2) = 2 * factorial(1) = 2 * 1 = 2

继续：

factorial(3) = 3 * 2 = 6

继续：

factorial(4) = 4 * 6 = 24

最后：

factorial(5) = 5 * 24 = 120

返回过程：

factorial(0)=1 ↑ factorial(1)=1 ↑ factorial(2)=2 ↑ factorial(3)=6 ↑ factorial(4)=24 ↑ factorial(5)=120

这一阶段就叫：

归

因为程序开始逐层返回结果。

为什么叫“先递后归”？

递归执行时并不会立即计算结果。

例如：

return5*factorial(4)

这里必须先知道：

factorial(4)

是多少。

而factorial(4)又需要知道：

factorial(3)

是多少。

于是程序只能不断向下调用。

5 -> 4 -> 3 -> 2 -> 1 -> 0

直到找到终止条件：

factorial(0)=1

然后才开始返回。

0 -> 1 -> 2 -> 3 -> 4 -> 5

所以递归本质上就是：

先递 后归

调用栈的变化

递归实际上依赖于栈（Stack）结构。

每调用一次函数，就会压入栈中。

栈顶 ┌─────────────┐ │ factorial(5)│ ├─────────────┤ │ factorial(4)│ ├─────────────┤ │ factorial(3)│ ├─────────────┤ │ factorial(2)│ ├─────────────┤ │ factorial(1)│ ├─────────────┤ │ factorial(0)│ └─────────────┘ 栈底

到达终止条件后开始出栈：

factorial(0) ↑ factorial(1) ↑ factorial(2) ↑ factorial(3) ↑ factorial(4) ↑ factorial(5)

这就是递归能够返回结果的根本原因。

递归的三大要素

任何递归都必须具备三个条件：

1. 递归函数

函数调用自己

factorial(n-1)

2. 终止条件

否则会无限递归

ifn==0:return1

3. 递推关系

当前问题可以拆分成更小的问题

factorial(n)=n*factorial(n-1)

总结

以阶乘为例：

deffactorial(n):ifn==0:return1returnn*factorial(n-1)

执行：

factorial(5)

经历了：

递： 5 → 4 → 3 → 2 → 1 → 0 归： 0 → 1 → 2 → 3 → 4 → 5

最终：

factorial(5) = 5 × 4 × 3 × 2 × 1 = 120

记住一句话：

递归不是边调用边计算，而是先一路调用到底，再一层一层返回结果。

这就是递归最核心的思想：

先递后归。