🔄 Recursion & Function Calls递归与函数调用

Understanding recursion and stack frame management理解递归原理与函数栈帧管理

What is Recursion?什么是递归？

Recursion is a technique where a function calls itself (directly or indirectly) to solve a problem by breaking it into smaller subproblems, until reaching a base case. 递归是一种编程技巧，函数直接或间接调用自身来解决问题。它将复杂问题分解为更小的同类问题，直至达到基准情况。

递归调用的栈帧变化：

factorial(5)
├── factorial(4)
│   ├── factorial(3)
│   │   ├── factorial(2)
│   │   │   ├── factorial(1)
│   │   │   │   └── return 1
│   │   │   └── return 1 * 1 = 1
│   │   └── return 2 * 1 = 2
│   └── return 3 * 2 = 6
└── return 4 * 6 = 24

// 阶乘函数的递归实现
int factorial(int n) {
    if (n == 0 || n == 1) {  // 基准情况
        return 1;
    } else {                   // 递归情况
        return n * factorial(n - 1);
    }
}
            

Three Elements of Recursion递归的三大要素

1. 基准情况（Base Case）

A recursion must have one or more base cases; otherwise, it results in infinite recursion and stack overflow. 递归必须有一个或多个终止条件，否则会导致无限递归和栈溢出。

int factorial(int n) {
    if (n <= 1) {          // 基准情况
        return 1;
    }
    // 递归调用
    return n * factorial(n - 1);
}
            

2. 递归情况（Recursive Case）

A recursive function calls itself and must move arguments towards the base case.函数调用自身，但参数必须向基准情况逐步接近。

3. 栈帧管理

Each recursive call creates a new stack frame with parameters, locals, and return address.每次递归调用都会创建新的栈帧，包含参数、局部变量和返回地址。

💡 递归 vs 迭代

递归：代码简洁，但开销较大
迭代：效率高，但可能代码复杂
选择：树形结构用递归，线性结构用迭代

Function Call Mechanism函数调用机制

Each function call creates a stack frame on the stack that includes:每次函数调用都会在栈上创建一个栈帧，包含：

函数参数
返回地址
局部变量
保存的寄存器

void function_a() {
    int x = 10;           // 局部变量
    function_b();           // 调用function_b
}

void function_b() {
    int y = 20;           // 局部变量
}
            

栈帧变化过程：

调用前: [main]
调用function_a: [main] -> [function_a: x=10]
调用function_b: [main] -> [function_a: x=10] -> [function_b: y=20]
function_b返回: [main] -> [function_a: x=10]
function_a返回: [main]

Countdown Launch Program倒计时发射程序

Let’s implement a classic Week 1 recursion exercise — a countdown launch program:让我们实现Week 1的经典递归练习——倒计时发射程序：

void perform_launch(int timer) {
    if (timer == 0) {          // 基准情况：发射！
        printf("Blast off!\n");
        return;
    }
    
    printf("%d\n", timer);     // 打印当前倒计时
    perform_launch(timer - 1); // 递归调用
}

// 使用示例
int main(int argc, char *argv[]) {
    if (argc != 2) {
        printf("Usage: %s \n", argv[0]);
        return 1;
    }
    
    int timer = atoi(argv[1]);
    perform_launch(timer);
    
    return 0;
}
            

🎯 执行示例

$ ./blast_off 5
5
4
3
2
1
Blast off!
                

Pros and Cons of Recursion递归的优缺点

优点：

Concise code, clear logic代码简洁，逻辑清晰
Natural fit for trees/graphs天然适合树形、图形等递归结构
Less duplicated code减少重复代码

缺点：

Consumes stack space栈空间消耗大
Risk of stack overflow可能存在栈溢出风险
Potentially less efficient效率相对较低

⚠️ 栈溢出

If recursion depth grows too large, the stack may overflow and crash. On Linux, default stack size is typically a few MB.当递归深度过大时，会耗尽栈空间导致程序崩溃。Linux系统默认栈大小通常为几MB。

// 危险的递归：可能导致栈溢出
void infinite_recursion() {
    infinite_recursion();  // 无限递归，栈溢出
}
                

🎯 Practice & Consolidation练习与巩固

练习1: 斐波那契数列

Implement Fibonacci with recursion: F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)用递归实现斐波那契数列：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)

int fibonacci(int n) {
    // 在这里实现斐波那契数列
    // 基准情况：n=0返回0，n=1返回1
    // 递归情况：F(n) = F(n-1) + F(n-2)
}
                

Answer:答案：

int fibonacci(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}
                    

练习2: 数组求和

Use recursion to sum an array without loops:用递归实现数组求和，不使用循环：

int array_sum(int *array, int size) {
    // 递归求数组元素和
    // 基准情况：size=0返回0
    // 递归情况：array[0] + array_sum(array+1, size-1)
}
                

Answer:答案：

int array_sum(int *array, int size) {
    if (size == 0) {
        return 0;
    } else {
        return array[0] + array_sum(array + 1, size - 1);
    }
}
                    

Summary总结

Recursion is a key concept in CS. In this module, you learned:递归是计算机科学中的重要概念，本周我们学习了：

递归原理：函数自我调用的机制
基准情况：确保递归终止的关键
栈帧管理：理解函数调用的底层实现
实际应用：倒计时、阶乘、斐波那契等
性能考虑：递归的优缺点和适用场景

🚀 Next Steps下一步学习

After mastering recursion, you’ve completed Week 1 core content. Next, explore advanced string handling and data structures.掌握了递归后，我们已经完成了Week 1的核心内容。接下来可以探索更高级的字符串处理和数据结构。

← 动态内存字符串 →