学编程的小伙伴，大概率都被递归折磨过。

“要理解递归，首先要理解递归”—— 这句话不是绕口令，而是递归最精髓的写照。

​

今天我们就用 “查字典” 和 “青蛙跳台阶” 两个例子，把递归的底层逻辑掰开揉碎，让你一看就懂，一写就会！

一、递归是什么？先从查字典说起

递归的本质，藏在我们日常查字典的行为里。

比如你想查 “千钧一发” 这个词：

1. 查 “千钧一发”，发现解释里的 “千钧” 看不懂，于是去查 “千钧”；
2. 查 “千钧”，看到 “一石为四钧”，又不懂 “一石”，再去查 “一石”；
3. 查到 “一石 = 120 斤”，这个解释完全明白，“递” 的过程就停止了；
4. 接下来开始 **“归”**：一石 = 120 斤 → 1 钧 = 30 斤 → 千钧 = 3 万斤 → 千钧一发的意思瞬间清晰！

这个过程就是递归的核心：先递后归

• 递
  ：把复杂问题拆成更小的子问题，子问题再拆，直到遇到一个 “不用再拆” 的终止条件（比如 “一石 = 120 斤”）。
• 归
  ：从终止条件的答案出发，反向推导，逐层解决上层问题，最终搞定最开始的复杂问题。

放到编程里，递归的定义更简单：函数自己调用自己，就是递归。

二、入门案例：阶乘计算，手把手写递归代码

递归的经典入门题，必须是阶乘计算。

什么是阶乘？

• n 的阶乘（记作 n!）= n × (n-1) × (n-2) × … × 1
• 特殊规定：1! = 1，0! = 1

1. 找规律：拆解问题

要计算 f(n)（n 的阶乘），我们可以拆成：f(n) = n × f(n-1)

比如：

• f(6) = 6 × f(5)
• f(5) = 5 × f(4)
• ...
• f(2) = 2 × f(1)
• f (1) = 1 （终止条件！不用再拆了）

2. 写代码：3 行搞定递归函数

def factorial(n):    # 终止条件：触底反弹的关键    if n == 1:        return 1    # 递：拆分子问题 + 归：合并结果    return n * factorial(n - 1)# 测试：计算6的阶乘print(factorial(6))  # 输出：720

3. 拆解执行过程：看清楚 “递” 和 “归”

计算 factorial(6) 的完整流程：

递的过程：f(6) = 6 × f(5)f(5) = 5 × f(4)f(4) = 4 × f(3)f(3) = 3 × f(2)f(2) = 2 × f(1)f(1) = 1 （终止）归的过程：f(2) = 2 × 1 = 2f(3) = 3 × 2 = 6f(4) = 4 × 6 = 24f(5) = 5 × 24 = 120f(6) = 6 × 120 = 720

看到没？递归根本不用 “人肉计算” 每一步，只要找对拆分规律和终止条件，代码会自己完成递和归！

三、进阶案例：青蛙跳台阶，递归思维的实战考验

搞懂阶乘还不够，我们来个更有意思的题 ——青蛙跳台阶，这可是面试高频题！

题目描述

一只青蛙一次可以跳 1 级台阶，也可以跳 2 级台阶。问：跳上第 n 级台阶，共有多少种跳法？

1. 找规律：从简单到复杂

先从 n 很小的情况入手，找规律：

• n=1：只有 1 种跳法（直接跳 1 级）→ f (1)=1
• n=2：两种跳法（1+1 / 直接跳 2 级）→ f (2)=2
• n=3：要跳到 3 级，最后一步只能是从 2 级跳 1 级，或者从 1 级跳 2 级 → f (3)=f (2)+f (1)=3
• n=4：同理，最后一步从 3 级或 2 级跳 → f (4)=f (3)+f (2)=5

规律总结：f(n) = f(n-1) + f(n-2)终止条件：f(1)=1，f(2)=2

这其实就是变形的斐波那契数列！

2. 写代码：递归版实现

def jump_floor(n):    # 终止条件    if n == 1:        return 1    elif n == 2:        return 2    # 递 + 归    return jump_floor(n-1) + jump_floor(n-2)# 测试：跳上第6级台阶的跳法数print(jump_floor(6))  # 输出：13

3. 验证执行过程

计算 jump_floor(6)：

递的过程：f(6) = f(5) + f(4)f(5) = f(4) + f(3)f(4) = f(3) + f(2)f(3) = f(2) + f(1)f(2)=2，f(1)=1 （终止）归的过程：f(3)=2+1=3f(4)=3+2=5f(5)=5+3=8f(6)=8+5=13

四、写递归代码的两个核心要点

看完两个例子，你会发现，写递归代码就两步，抓住了就不会错：

1. 找递推公式：如何拆分问题？

把大问题 f(n) 拆成子问题的组合，比如：

• 阶乘：f(n) = n × f(n-1)
• 青蛙跳台阶：f(n) = f(n-1) + f(n-2)

这一步的关键是自上而下思考：要解决 f (n)，我需要先解决什么子问题？

2. 定终止条件：什么时候停止？

递归不能无限 “递” 下去，必须有一个 “底线”—— 当问题小到可以直接给出答案时，就停止递归，开始 “归”。

比如阶乘的 n=1，青蛙跳台阶的 n=1 和 n=2。没有终止条件的递归，会变成死循环，直接栈溢出！

递归一点都不神秘，记住这句话就行：递归 = 递（拆分子问题） + 归（合并子问题答案）

写递归代码的步骤：

1. 分析问题，找到递推公式（大问题拆小问题）；
2. 确定终止条件（最小子问题的答案）；
3. 把递推公式和终止条件翻译成代码。

下次再遇到递归题，别慌，先找递推公式，再定终止条件，剩下的交给代码就好啦！

阅读原文：原文链接