第 10 课 - 递归基础

学习目标

理解递归的概念及其在解决问题中的核心思想。
掌握构成递归的三个基本要素：基本情况、递归情况和向基本情况靠近。
了解递归函数调用过程中“调用栈”的概念。
能够运用递归编写简单的函数，如计算阶乘、斐波那契数列等。

核心概念

什么是递归？

想象一下俄罗斯套娃。当你打开一个大娃娃，里面有一个小一点的娃娃，再打开，里面还有一个更小的……直到你打开一个最小的、不能再打开的娃娃。这个过程就是递归。在编程中，递归是指一个函数在执行过程中直接或间接地调用自身来解决问题的技术。

递归的核心思想是 “分而治之”：将一个大问题（大娃娃）分解为一个或多个与原问题相似但规模更小的小问题（小娃娃），然后持续分解，直到问题变得足够简单，可以直接解决（最小的娃娃）。

递归三要素

一个正确的递归函数必须包含以下三个要素，缺一不可：

基本情况 (Base Case)：也称为递归出口。这是问题的最简形式，可以直接给出答案而不需要再次调用自身。它是递归的“刹车”，防止无限循环。就像套娃游戏必须有一个最小的、不能再打开的娃娃一样。
递归情况 (Recursive Case)：这是函数调用自身的部分。它将当前问题分解成一个或多个更小的、与原问题结构相同的子问题。
向基本情况靠近 (Progress Toward Base Case)：每一次递归调用，问题的规模都必须更接近基本情况。否则，递归将永远无法停止，导致“栈溢出”错误。

调用栈 (Call Stack)

当函数被调用时，计算机会在内存中一个叫做“栈”的特殊区域为它分配一块空间，称为栈帧。这个栈帧里存放着函数的局部变量和执行到的位置等信息。当一个递归函数调用自身时，一个新的栈帧会被压入栈顶。当一次调用执行完毕返回时，它的栈帧会从栈顶弹出，控制权交还给它下面的那个调用。

理解调用栈有助于我们明白递归是如何工作的：每一次递归调用都是一个独立的“子任务”，它们像积木一样一层层堆叠起来，当最顶层的子任务完成后，结果被依次传递回下层。

代码示例

示例 1：阶乘 (Factorial)

阶乘的数学定义是：n! = n * (n-1) * (n-2) * ... * 1，且 0! = 1。这个定义天然具有递归结构：n! = n * (n-1)!。

def factorial(n):
    """
    使用递归计算n的阶乘。
    :param n: 非负整数
    :return: n的阶乘结果
    """
    # 1. 基本情况 (Base Case)
    if n == 0 or n == 1:
        return 1
    
    # 2. 递归情况 (Recursive Case) + 3. 向基本情况靠近 (n变小)
    return n * factorial(n - 1)

# 测试
print(factorial(5))  # 输出: 120
print(factorial(0))  # 输出: 1

执行流程分析： factorial(5) 调用 factorial(4), factorial(4) 调用 factorial(3)……直到 factorial(1) 返回 1。然后结果层层返回：1 * 1 = 1，2 * 1 = 2，3 * 2 = 6，4 * 6 = 24，5 * 24 = 120。

示例 2：斐波那契数列 (Fibonacci Sequence)

斐波那契数列定义为：F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) (n>=2)。

def fibonacci(n):
    """
    使用递归计算斐波那契数列的第n项。
    :param n: 非负整数
    :return: 第n项的值
    """
    # 1. 基本情况
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    # 2. 递归情况 + 3. 向基本情况靠近
    return fibonacci(n - 1) + fibonacci(n - 2)

# 测试
print(fibonacci(6))  # 输出: 8 (序列: 0,1,1,2,3,5,8)
print(fibonacci(10)) # 输出: 55

示例 3：字符串反转 (String Reversal)

将一个字符串反转，例如 “hello” 变成 “olleh”。递归思路：reverse(“hello”) = reverse(“ello”) + “h”。

def reverse_string(s):
    """
    使用递归反转字符串。
    :param s: 输入字符串
    :return: 反转后的字符串
    """
    # 1. 基本情况：空字符串或只有一个字符
    if len(s) <= 1:
        return s
    
    # 2. 递归情况：反转除第一个字符外的子串，再拼接上第一个字符
    # “向基本情况靠近”体现在每次调用，字符串长度减1
    return reverse_string(s[1:]) + s[0]

# 测试
print(reverse_string("hello"))    # 输出: "olleh"
print(reverse_string("algorithm")) # 输出: "mhtirogla"

实践练习

练习 1：计算列表元素之和

编写一个递归函数 list_sum(lst)，计算一个整数列表（如 [1, 2, 3, 4, 5]）中所有元素的和。要求：

明确写出基本情况和递归情况。
使用切片 lst[1:] 来缩小问题规模。 预期输出：

print(list_sum([1, 2, 3, 4, 5])) # 输出: 15
print(list_sum([10, -5, 3]))      # 输出: 8

练习 2：字符串回文判断

编写一个递归函数 is_palindrome(s)，判断一个字符串（忽略大小写）是否是回文（正读反读都一样，如 “racecar”）。提示：比较首尾字符，并递归检查中间的子串。 预期输出：

print(is_palindrome("racecar"))  # 输出: True
print(is_palindrome("hello"))    # 输出: False
print(is_palindrome("Madam"))    # 输出: True

练习 3（挑战）：汉诺塔 (Tower of Hanoi)

这是一个经典的递归问题。有三根柱子A、B、C和n个大小不同的圆盘，起初所有圆盘按从小到大的顺序堆叠在柱子A上。目标是将所有圆盘移动到柱子C上，每次只能移动一个盘子，且大盘子不能放在小盘子上面。编写一个递归函数 hanoi(n, source, target, auxiliary)，打印出移动步骤。提示：将移动n个盘子的问题分解为：

将n-1个盘子从source借助target移动到auxiliary。
将第n个盘子从source移动到target。
将n-1个盘子从auxiliary借助source移动到target。 预期输出 (n=3时):

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

常见错误

忘记基本情况：这是最常见的错误。没有基本情况，递归函数会无限调用自身，最终导致程序崩溃（栈溢出错误 RecursionError: maximum recursion depth exceeded）。
基本情况不正确或不完整：例如在阶乘中，只写了 if n == 1: return 1，而忽略了 n == 0 的情况。
递归调用没有向基本情况靠近：例如写了一个函数 def f(n): return f(n) + 1，n 值始终不变，递归永远不会结束。
混淆返回值：在递归调用中，忘记返回递归调用的结果。例如写成了 fibonacci(n-1) + fibonacci(n-2) 而漏掉了 return。
过度递归：对于某些问题（如朴素的斐波那契递归），递归效率极低，因为做了大量的重复计算。对于这类问题，可以使用“记忆化”（Memoization）技术来优化。

小结

本节课我们学习了递归这一强大而优雅的编程技巧。关键要点回顾如下：

递归本质：函数调用自身，将大问题分解为相似的小问题。
递归三要素：必须包含基本情况（终止条件）、递归情况（自我调用）、以及确保每次调用都向基本情况靠近。
理解调用栈：递归函数的每一次调用都在内存栈中创建一个新的栈帧，执行完成后按后进先出的顺序返回结果。
适用场景：递归特别适用于那些可以自然分解为相似子问题的场景，如数学定义（阶乘、斐波那契）、数据结构遍历（树、图）、分治算法等。
权衡与思考：虽然递归代码通常简洁清晰，但可能带来函数调用开销和栈空间消耗。对于某些问题，将其转化为迭代（循环）解法可能更高效。

掌握递归思维是学习数据结构与算法的重要一步。下一课，我们将学习排序算法中的“冒泡排序”，在那里你可能会看到循环和递归思想在不同解法中的体现。请务必通过实践练习来巩固今天所学的内容！

练习编辑器

rust