c语言递归调用举例加解析

C语言函数的递归调用是指在函数内部调用自身的过程。递归调用可以让问题变得更简单，因为它可以将一个大问题分解成多个小问题，然后逐个解决这些小问题。递归调用需要满足两个条件：基本情况和递归情况。基本情况是指递归调用结束的条件，递归情况是指函数内部调用自身的情况。在递归调用中，每次调用都会将一部分数据压入栈中，直到递归结束后再依次弹出栈中的数据，因此递归调用需要注意栈溢出的问题。 举例来说，引用中的代码就是一个利用递归求100以内所有数相加之和的例子。在这个例子中，递归函数digui(n)的基本情况是当n小于1时返回0，递归情况是当n大于等于1时返回n加上digui(n-1)的值。在主函数中调用digui(100)即可求出100以内所有数相加之和。 引用中的代码则是一个用递归方法打印出斐波拉契数列的例子。在这个例子中，递归函数feibolaqi(n)的基本情况是当n小于等于2时返回1，递归情况是当n大于2时返回feibolaqi(n-1)加上feibolaqi(n-2)的值。在主函数中调用feibolaqi(i)即可求出斐波拉契数列中的第i个数。

<think>我们正在学习C语言中的递归调用。递归是一种函数直接或间接调用自身的技术，它通过将大问题分解为相似的小问题来简化代码。递归有两个必要条件：存在递归出口（终止条件）和每次递归调用都向终止条件靠近。根据引用[2]，递归有三个要素：1.终止条件（Base Case）：递归必须有一个明确的结束条件，否则会无限递归，导致栈溢出。2.递归调用（Recursive Call）：函数调用自身来解决更小的子问题。3.递归前进段和回溯段：递归调用之前是前进段，之后是回溯段。引用[4]提醒我们，递归调用会使用调用栈（call stack），每次调用都会在栈上压入一个新的栈帧（包含局部变量、参数和返回地址）。如果递归深度太大，栈空间会被耗尽，导致程序崩溃。下面通过多个示例来理解递归： ###示例1：计算阶乘（Factorial）阶乘的数学定义：$n!= n\times(n-1)!$，其中$0! =1$这是一个经典的递归问题，因为大问题（n!）可以分解为小问题（(n-1)!）。 ```c#include<stdio.h>//递归计算阶乘long factorial(int n) {//终止条件：0! =1if (n ==0) {return1;}//递归调用：n! =n *(n-1)!returnn *factorial(n-1);} intmain(){int n=5;printf("%d!= %ld\n", n, factorial(n));//输出：120return0; }```**调用栈分析**（以n=3为例）：factorial(3)->3* factorial(2)->2 *factorial(1)->1* factorial(0)->返回1返回1*1=1返回2*1=2返回3*2=6###示例2：斐波那契数列（Fibonacci）斐波那契数列定义：$F(0)=0,F(1)=1$$F(n) =F(n-1) +F(n-2)$（当n>=2）注意：这个递归实现效率很低（指数级），因为存在大量重复计算。实际中应使用迭代或记忆化优化。 ```c#include<stdio.h>int fib(int n) {//终止条件if(n==0)return0;if(n==1)return1;//递归调用：F(n) =F(n-1) +F(n-2)return fib(n -1) +fib(n-2);} intmain(){int n=6;printf("F(%d) =%d\n",n,fib(n)); //输出：8return0; }``` **调用树分析**（fib(4)）：```fib(4)/\fib(3)fib(2)/\/\ fib(2) fib(1) fib(1) fib(0)/\ fib(1) fib(0)```可以看到fib(2)被计算了两次，fib(1)和fib(0)被计算多次。 ###示例3：汉诺塔（Towerof Hanoi）汉诺塔问题是一个经典的递归问题。规则：-有三根柱子A、B、C，A柱上有n个大小不同的圆盘（从上到下从小到大）。-每次移动一个圆盘，且大盘不能放在小盘上面。-目标：将所有圆盘从A移到C，B作为辅助柱。递归思路：1.将n-1个圆盘从A移到B（借助C）2.将第n个圆盘（最大的）从A移到C3.将n-1个圆盘从B移到C（借助A）```c#include <stdio.h> voidhanoi(int n, charfrom, charto,char aux) {if(n==1){//终止条件：只有一个盘子时，直接移动printf("Movedisk1 from%c to%c\n",from,to);return;}//递归步骤1：将n-1个盘子从起始柱移动到辅助柱（目标柱作为辅助）hanoi(n-1,from,aux,to);//移动第n个盘子printf("Movedisk %d from%cto %c\n", n, from, to);//递归步骤2：将n-1个盘子从辅助柱移动到目标柱（起始柱作为辅助）hanoi(n-1,aux,to,from);} intmain(){int n=3;hanoi(n, 'A','C', 'B');//将n个盘子从A移到C，借助Breturn0; }``` **输出**： ```Move disk1from Ato CMovedisk2 fromA toBMove disk1from Cto BMovedisk3 fromA toCMove disk1from Bto AMovedisk2 fromB toCMove disk1from Ato C```###示例4：递归求数组最大值递归也可以用于处理数组。例如，求数组最大值：-终止条件：数组只有一个元素，最大值就是它本身。-递归步骤：将数组分成两部分，分别求两部分的最大值，然后返回两者中的较大者。```c#include <stdio.h> intmax(inta,int b) {return a> b? a: b; }intfindMax(int arr[], intstart,int end) {//终止条件：数组只有一个元素if(start== end) {returnarr[start];}//将数组分成两部分（分治）intmid =(start+ end) /2;int leftMax =findMax(arr,start,mid);intrightMax= findMax(arr, mid+1,end);//合并：返回左右两部分的最大值return max(leftMax, rightMax);} intmain(){int arr[] ={3,5,2,9,7,1};int n= sizeof(arr)/ sizeof(arr[0]);printf("Maxvalue:%d\n",findMax(arr,0, n-1)); //9return0;} ```###递归的优缺点**优点**：-代码简洁，表达力强-适合解决分治、树和图等问题**缺点**：-递归调用会消耗栈空间，深度过大时可能导致栈溢出-重复计算（如斐波那契数列）-函数调用开销比循环大因此，在使用递归时，要注意：-确保有终止条件，且每次递归都向终止条件靠近-对于深度大的递归，考虑迭代（循环）或尾递归优化（但C语言标准不保证尾递归优化）-避免重复计算，可用记忆化（缓存结果）技术###尾递归尾递归是指递归调用是函数的最后一步操作。某些编译器可以优化尾递归，使其不增加栈深度（相当于循环）。例如阶乘的尾递归版本： ```clong factorial_tail(intn,long result) {if(n==0){return result;}//尾递归：返回递归调用本身，且没有其他操作returnfactorial_tail(n-1,n *result);} //调用时：factorial_tail(5,1);```注意：不是所有递归都能写成尾递归，且编译器优化尾递归不是C标准强制要求的。通过以上示例，你应该对递归有了基本理解。请尝试自己编写递归函数，如计算数组和、字符串反转等。 §§相关问题§§1.如何避免递归中的重复计算？2.递归和迭代（循环）在性能上有什么区别？3.什么是递归的调用栈？如何避免栈溢出？4.尾递归优化是如何工作的？5.请用递归实现二分查找算法。</think>### C语言递归调用详解 递归是函数直接或间接调用自身的技术，通过将复杂问题分解为相似的小问题来求解。递归有两个核心条件： 1. **递归出口**：必须存在终止条件，防止无限递归 2. **递归前进**：每次递归调用必须使问题规模更接近终止条件 #### 递归三要素 1. **终止条件**（Base Case）：递归结束的条件 2. **递归调用**：函数调用自身解决子问题 3. **问题分解**：将原问题转化为更小的相似问题 --- ### 递归示例代码 #### 示例1：阶乘计算（基本递归） ```c #include <stdio.h> // 递归计算阶乘 int factorial(int n) { // 终止条件：0! = 1 if (n == 0) { return 1; } // 递归调用：n! = n * (n-1)! return n * factorial(n - 1); } int main() { int num = 5; printf("%d! = %d\n", num, factorial(num)); // 输出：120 return 0; } ``` **执行过程**： ``` 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：斐波那契数列（多重递归） ```c #include <stdio.h> int fibonacci(int n) { // 终止条件 if (n <= 1) { return n; } // 递归调用：F(n) = F(n-1) + F(n-2) return fibonacci(n - 1) + fibonacci(n - 2); } int main() { printf("F(6) = %d\n", fibonacci(6)); // 输出：8 return 0; } ``` **调用树**： ``` fibonacci(6) ├─ fibonacci(5) │ ├─ fibonacci(4) │ │ ├─ fibonacci(3) │ │ │ ... │ └─ fibonacci(3) └─ fibonacci(4) ... ``` #### 示例3：汉诺塔问题（经典递归） ```c #include <stdio.h> void hanoi(int n, char from, char to, char aux) { // 终止条件：只有一个盘子 if (n == 1) { printf("将盘子 1 从 %c 移动到 %c\n", from, to); return; } // 递归步骤1：将n-1个盘子移到辅助柱 hanoi(n - 1, from, aux, to); // 移动第n个盘子 printf("将盘子 %d 从 %c 移动到 %c\n", n, from, to); // 递归步骤2：将n-1个盘子移到目标柱 hanoi(n - 1, aux, to, from); } int main() { hanoi(3, 'A', 'C', 'B'); // 3个盘子从A移到C return 0; } ``` **输出**： ``` 将盘子 1 从 A 移动到 C 将盘子 2 从 A 移动到 B 将盘子 1 从 C 移动到 B 将盘子 3 从 A 移动到 C 将盘子 1 从 B 移动到 A 将盘子 2 从 B 移动到 C 将盘子 1 从 A 移动到 C ``` #### 示例4：递归求数组和（分治思想） ```c #include <stdio.h> int array_sum(int arr[], int start, int end) { // 终止条件：单个元素 if (start == end) { return arr[start]; } // 分解问题：中点分割 int mid = (start + end) / 2; // 递归求解子数组和 return array_sum(arr, start, mid) + array_sum(arr, mid + 1, end); } int main() { int arr[] = {1, 3, 5, 7, 9}; int size = sizeof(arr) / sizeof(arr[0]); printf("数组和: %d\n", array_sum(arr, 0, size - 1)); // 输出：25 return 0; } ``` --- ### 递归调用机制 1. **调用栈**：每次递归调用在栈中创建新栈帧 - 包含局部变量、参数和返回地址 - 栈帧累积过多会导致**栈溢出**（Stack Overflow） 2. **执行阶段**： - **前进阶段**：递归调用直到终止条件 - **回溯阶段**：从终止条件开始逐层返回结果 ```c void recursive_func(int n) { if (n <= 0) return; // 终止条件 recursive_func(n - 1); // 递归调用 } ``` **栈帧变化**（n=3）： ``` | n=0 | ← 栈顶 | n=1 | | n=2 | | n=3 | ← 栈底 ``` --- ### 递归注意事项 1. **栈溢出风险**：递归深度过大耗尽栈空间 ```c void infinite_recursion() { infinite_recursion(); // 无限递归导致崩溃 } ``` 2. **效率问题**：斐波那契等存在重复计算 - 解决方案：记忆化（缓存结果） 3. **尾递归优化**：某些编译器可将尾递归转为循环 ```c int factorial_tail(int n, int result) { if (n == 0) return result; return factorial_tail(n - 1, n * result); // 尾递归 } ``` --- ### 递归 vs 迭代 | 特性 | 递归 | 迭代 | |--------------|--------------------------|-------------------| | **代码简洁性** | 高（符合问题自然结构） | 较低 | | **内存使用** | 栈空间（可能溢出） | 固定内存 | | **性能** | 函数调用开销大 | 通常更快 | | **适用场景** | 树/图遍历、分治算法 | 简单循环任务 | --- ###