【Daily-Algorithm-7】每日算法学习（第七天）—— 递归算法基础，从原理到实战（Python 实现）

递归，作为编程中极具魅力的算法思想，核心是函数调用自身，将复杂问题拆解为规模更小的同类子问题，直到触达 “边界条件”（递归出口）后逐层回溯，最终解决原问题。这种 “大事化小、小事化了” 的思路，能让代码简洁优雅，尤其适合解决具有重复子结构的问题。

本文将通过 4 个经典实例，带你吃透递归的核心逻辑，所有代码均可直接运行，建议结合注释逐行理解递归的 “递” 与 “归”。

一、阶乘算法：递归的入门典范

阶乘是递归最基础的应用场景。数学上，n!（n 的阶乘）定义为：

• 边界条件：0! = 1（0 的阶乘为 1，是人为规定的递归出口）
• 递归关系：n! = n × (n-1)!（n>0 时，n 的阶乘等于 n 乘以 n-1 的阶乘）

代码实现：

#阶乘运算 def factorial(n): if n==0: return 1 else: return factorial(n-1)*n n=int(input()) print(f'{n}的阶乘为{factorial(n)}')

逻辑解析：以计算5!为例，递归的执行过程是 “先递后归”：

1. 递：factorial(5) → 调用factorial(4) → 调用factorial(3) → 调用factorial(2) → 调用factorial(1) → 调用factorial(0)；
2. 归：factorial(0)返回 1 → factorial(1)=1×1=1 → factorial(2)=1×2=2 → factorial(3)=2×3=6 → factorial(4)=6×4=24 → factorial(5)=24×5=120。

二、斐波那契数列：递归解决递推关系问题

斐波那契数列是经典的递推数列，其核心规律为：

• 边界条件：第 1 位和第 2 位均为 1（F(1)=1，F(2)=1）；
• 递归关系：从第 3 位开始，每一位等于前两位之和（F(n) = F(n-1) + F(n-2)）。

代码实现：

#第n个斐波那契数 def fibonacci(n): if n==1 or n==2: return 1 else: return fibonacci(n-1) + fibonacci(n-2) n=int(input()) print(f'第{n}个斐波那契数为{fibonacci(n)}')

逻辑解析：计算第 5 个斐波那契数时，递归会拆解为：fibonacci(5) = fibonacci(4) + fibonacci(3)fibonacci(4) = fibonacci(3) + fibonacci(2)fibonacci(3) = fibonacci(2) + fibonacci(1)当触达n=1或n=2的边界条件后，开始回溯求和，最终得到fibonacci(5)=5。

注：纯递归实现斐波那契数列存在重复计算问题（如fibonacci(3)会被计算多次），适合理解递归逻辑；实际开发中可结合记忆化缓存优化效率。

三、全排列问题：递归拆解 “选元素 + 排剩余”

全排列是指从 n 个不同元素中取出所有元素，按任意顺序排列，最终得到所有可能的排列组合。递归解决全排列的核心思路是：

• 边界条件：若列表只剩 1 个元素，其全排列就是自身；
• 递归关系：遍历列表中的每个元素，将其作为 “第一个元素”，再对剩余元素递归求全排列，最终拼接所有结果。

代码实现：

#全排列问题 def full_permutation(list): if len(list)==1: #如果列表中的元素仅有一个，那么直接输出 return [list] #返回[list]而非list，保证递归拼接类型一致 result=[] for i in range(len(list)): #遍历列表 first=list[i] #选择任意一个作为第一个 rest=list[:i]+list[i+1:] #构造剩余元素组成的列表 for j in full_permutation(rest): #递归，对剩余元素组成的列表如上操作，接着第二个位置往后依次添加 result.append([first]+j) #将元素依次添加到result中 return result #用eval解析输入字符串为真正的列表 list=eval(input("请输入列表，例如[1,2,3]:")) for p in full_permutation(list): print(p)

逻辑解析：以列表[1,2,3]为例：

1. 先选 1 作为第一个元素，剩余[2,3]，递归求[2,3]的全排列（[[2,3],[3,2]]），拼接得到[[1,2,3],[1,3,2]]；
2. 再选 2 作为第一个元素，剩余[1,3]，递归求全排列后拼接得到[[2,1,3],[2,3,1]]；
3. 最后选 3 作为第一个元素，剩余[1,2]，递归求全排列后拼接得到[[3,1,2],[3,2,1]]；
4. 所有结果合并，得到[1,2,3]的 6 种全排列。

四、汉诺塔问题：递归解决 “分步移动” 类问题

汉诺塔是递归的经典应用，问题规则为：

• 有 A、B、C 三根柱子，A 柱有 n 个大小递减的盘子（大盘在下、小盘在上）；
• 每次只能移动 1 个盘子，且任何时候大盘不能放在小盘上；
• 目标是将 A 柱所有盘子移到 C 柱，B 柱作为过渡。

递归解决汉诺塔的核心思路：

• 边界条件：若只有 1 个盘子，直接从 A 移到 C；
• 递归关系：
  1. 先将 A 柱上 n-1 个盘子从 A 移到 B（以 C 为过渡）；
  2. 将 A 柱最后 1 个大盘移到 C；
  3. 再将 B 柱上 n-1 个盘子从 B 移到 C（以 A 为过渡）。

代码实现：

#汉诺塔问题 def hanoi(n,start,mid,end): if n==1: #只有一个盘子，直接从start移动到end print(start,"-->",end) #代表从start处移动一个盘子到end处 return #先把把上面的n-1个盘子移动到mid处，才能移动最下面的那个最大的盘子（注意顺序） hanoi(n-1,start,end,mid) print(start,"-->",mid) #再把中间的n-1个移动到end，进行递归操作 hanoi(n-1,mid,start,end) n=int(input()) if __name__ =="__main__": hanoi(n,"A","B","C")

逻辑解析：以 n=2 为例，执行过程：

1. 调用hanoi(1,A,C,B)，触发边界条件，打印A --> B；
2. 打印A --> B（移动第 2 个盘子）；
3. 调用hanoi(1,B,A,C)，触发边界条件，打印B --> C；最终完成 2 个盘子从 A 到 C 的移动（实际输出可结合规则验证步骤合理性）。

递归算法核心总结

1. 递归三要素：明确边界条件（递归出口，避免无限递归）、定义递归关系（将大问题拆为小问题）、确定返回值（保证回溯时能正确拼接结果）；
2. 执行逻辑：始终遵循 “先递后归”—— 先逐层拆解问题到边界条件，再从边界条件开始回溯计算，最终得到原问题答案；
3. 适用场景：适合解决具有 “重复子结构” 的问题（如阶乘、斐波那契、全排列、汉诺塔），但需注意递归深度（Python 默认递归深度有限）和重复计算问题，必要时结合缓存、迭代优化。

递归的本质是 “自顶向下” 的问题拆解，掌握它不仅能简化代码，更能培养 “分而治之” 的编程思维。建议结合上述实例手动推演执行过程，理解每一步的 “递” 与 “归”，真正吃透递归的核心逻辑。