一、递归到底是什么？

递归 = 函数自己调用自己

就像两面镜子对着照，无限反射，但必须有出口（不然会卡死）。

---

二、递归的 2 个核心

1. 基线条件（出口）

   不再调用自己，直接返回结果，防止无限循环。

   if n == 1:
       return 1
   

2. 递归条件（自己调用自己）

   把问题缩小一点

   return n * fact(n-1)
   

---

三、阶乘 fact (5) 到底怎么算？

我给你画成最直白的步骤，一看就懂：

fact(5)
= 5 * fact(4)
= 5 * 4 * fact(3)
= 5 * 4 * 3 * fact(2)
= 5 * 4 * 3 * 2 * fact(1)
= 5 * 4 * 3 * 2 * 1
= 120

一层层进去，再一层层算出来。

---

四、尾递归是什么？（简单理解）

普通递归：

return n * fact(n-1)

带着算式进去 → 占内存 → 多了会爆栈。

尾递归：

return fact_iter(n-1, n*product)

只调用自己，不带表达式 → 理论上不占额外内存。

但！Python 不优化尾递归，所以不用纠结。

---

五、汉诺塔练习（我给你讲明白）

汉诺塔就是 3 步：

1. 把 n-1 个盘子 A → B
2. 把最后 1 个盘子 A → C
3. 把 n-1 个盘子 B → C

完整代码（直接运行）

def move(n, a, b, c):
    if n == 1:
        print(a, '-->', c)
    else:
        move(n-1, a, c, b)  # 1. n-1 个 A → B
        move(1, a, b, c)    # 2. 最后 1 个 A → C
        move(n-1, b, a, c)  # 3. n-1 个 B → C

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

输出（完全正确）

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

---

六、必须记住的 3 句话

1. 递归 = 函数自己调用自己
2. 必须有出口（n==1 这种）
3. 每次调用都让问题变小

分割线

return作用

return 的作用只有一个：

把结果送出去，并且立刻结束当前这个函数

===分割线=代码分析

先给代码 → 逐句讲为什么这么写 → 再完整走一遍程序是怎么走的。

完整代码

def fact (n):
    if n==1:
        return 1
    else:
        return  n * fact(n-1)
print(fact(3))

return后存在哪了？一句话总结

return 的值，不是存在某个地方，

而是一层一层往上交，

直到交给最开始调用函数的地方。

你可以把它理解成：

• 一层问下一层：“结果是多少？”
• 下一层 return 一个数
• 上一层拿到这个数，继续算

---

一、每一句为什么要这么写？

1. def fact(n):

• 定义一个名字叫 fact 的函数
• 作用：计算 n 的阶乘（n! = 1×2×3×…×n）
• n 是要计算的数字

2. if n == 1:

• 递归必须有出口，不能无限调用自己
• 数学上规定：1! = 1
• 当 n 变成 1 时，我们就知道结果了，不用再往下拆

3. return 1

• 返回结果 1
• 直接结束当前这个函数调用，后面的 else 不会再执行

4. else:

• 当 n 不是 1 的时候，才走这里
• 意思：还需要继续递归计算

5. return n * fact(n - 1)

• 阶乘公式：n! = n × (n-1)!
• 想算 n 的阶乘，就要先算出 n-1 的阶乘
• fact(n-1) 就是再调用一次自己，把问题变小一点

---

二、程序实际怎么走？（以 fact (3) 举例）

我们调用：

print(fact(3))

第 1 步：进入 fact (3)

• n = 3
• n == 1？不成立
• 走 else
• 要执行：return 3 * fact(2)
• 程序停下来，先去算 fact (2)

第 2 步：进入 fact (2)

• n = 2
• n == 1？不成立
• 走 else
• 要执行：return 2 * fact(1)
• 程序又停下来，先去算 fact (1)

第 3 步：进入 fact (1)

• n = 1
• n == 1？成立
• 执行 return 1
• 这个函数结束，返回结果 1

第 4 步：回到 fact (2)

• 刚才 fact (1) 算出来是 1
• 所以：2 * 1 = 2
• 返回结果 2

第 5 步：回到 fact (3)

• 刚才 fact (2) 算出来是 2
• 所以：3 * 2 = 6
• 返回结果 6

---

最终结果

6

====分割线=