Python进阶之递归函数的用法及其示例
最新回答
憇憇圏
2026-10-30 17:37:06
递归函数是Python中一种强大的编程技术，它允许函数直接或间接调用自身以解决问题。以下是递归函数的详细用法及示例：
递归函数的核心在于将问题分解为更小的子问题，直到达到一个已知的简单情况（即终止条件），然后逐层返回结果。以下是递归函数的关键要点：
- 终止条件：递归必须有一个明确的终止条件，否则会导致无限递归，最终引发栈溢出错误。
- 递推与回溯：
递推：将问题逐步分解为更小的子问题。
回溯：在达到终止条件后，逐层返回结果，完成计算。
阶乘是一个经典的递归问题。n的阶乘（记作n!）是所有小于及等于n的正整数的乘积，且0! = 1。
def factorial(n): if n == 0: # 终止条件 return 1 else: return n * factorial(n - 1) # 递归调用# 测试print(factorial(5)) # 输出: 120计算过程：
factorial(5)= 5 * factorial(4)= 5 * (4 * factorial(3))= 5 * (4 * (3 * factorial(2)))= 5 * (4 * (3 * (2 * factorial(1))))= 5 * (4 * (3 * (2 * (1 * factorial(0)))))= 5 * (4 * (3 * (2 * (1 * 1)))) # 达到终止条件= 120示例2：斐波那契数列斐波那契数列是一个每个数字都是前两个数字之和的数列，通常以F(0) = 0和F(1) = 1开始。
def fibonacci(n): if n <= 1: # 终止条件 return n else: return fibonacci(n - 1) + fibonacci(n - 2) # 递归调用# 测试print(fibonacci(6)) # 输出: 8计算过程：
fibonacci(6)= fibonacci(5) + fibonacci(4)= (fibonacci(4) + fibonacci(3)) + (fibonacci(3) + fibonacci(2))= ((fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))) + ((fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0)))= ... (继续分解直到达到终止条件)= 8示例3：汉诺塔问题汉诺塔是一个经典的递归问题，涉及将一组盘子从一个柱子移动到另一个柱子，遵循以下规则：
- 一次只能移动一个盘子。
- 每次移动时，将最上面的盘子移动到某一柱子上。
- 大盘子不能放在小盘子上面。
输出：
Move disk 1 from A to CMove disk 2 from A to BMove disk 1 from C to BMove disk 3 from A to CMove disk 1 from B to AMove disk 2 from B to CMove disk 1 from A to C递归的优缺点优点：
代码简洁，易于理解。
适合解决分治问题，如树的遍历、图的搜索等。
缺点：
递归调用会占用较多的栈空间，可能导致栈溢出。
效率较低，因为存在重复计算（如斐波那契数列的简单递归实现）。
为了避免重复计算，可以使用记忆化技术（Memoization）来存储已计算的结果，从而提高效率。
def fibonacci_memo(n, memo={}): if n in memo: return memo[n] if n <= 1: return n memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo) return memo[n]# 测试print(fibonacci_memo(50)) # 输出: 12586269025通过记忆化，斐波那契数列的计算效率显著提高，避免了重复计算。
热门标签
