【C语言基础】：函数递归详解

大家好，欢迎来到IT知识分享网。

         书山有路勤为径，学海无涯苦作舟。
创作不易，宝子们！如果这篇文章对你们有帮助的话，别忘了给个免费的赞哟~

一、基础概念

1. 函数递归的概念

函数递归指的是在函数内部调用自身的过程。
具体而言，递归函数通过将一个问题分解为更小的、类似的子问题来解决问题。

2. 递归函数的定义

递归函数的定义通常包括以下几个要素：

• 基本情况（Base Case）：递归函数必须包含一个或多个基本情况，即能够直接解决的最简单的问题。当函数达到基本情况时，递归将停止。基本情况提供了递归终止的条件。
• 递归调用（Recursive Call）：递归函数在解决复杂问题时会调用自身，但每次调用时问题规模会减小，直到达到基本情况。递归调用是递归函数实现的关键，它使得函数能够重复地处理子问题。
• 问题规模减小：递归调用必须保证问题规模在每次递归时都减小，否则递归可能无法终止。通过每次递归调用都将问题规模减小，最终达到基本情况。

3. 函数递归的优缺点

优点：

• 简化问题：递归能够将复杂问题分解成更小、更简单的子问题，使得代码逻辑更加清晰和简洁。递归能够提高代码的可读性和可维护性。
• 解决递归问题：对于某些问题，递归是一种自然且直接的解决方案。递归能够提供一种直观的思考方式，使得问题的解决过程更加容易理解。
• 适应动态规划：递归和动态规划（DP）问题密切相关。在动态规划中，递归函数可以用来定义子问题之间的关系，帮助我们设计出高效的算法。

缺点：

• 性能开销：递归调用涉及函数的多次调用、参数传递和栈的操作，这会引入额外的性能开销。相比迭代循环，递归可能会导致更长的执行时间和更多的内存消耗。
• 栈溢出：如果递归深度过大或者没有正确的终止条件，递归函数可能会导致栈溢出，从而导致程序崩溃。因此，在使用递归时，必须小心控制递归的深度，确保终止条件能够被满足。
• 可读性挑战：尽管递归可以简化代码逻辑，但对于复杂的递归函数，理解和调试可能会比较困难。递归的实现需要深入思考问题的分解和合并过程，对于初学者来说可能会有一定的难度。
• 隐式堆栈：递归调用会创建隐式的函数调用堆栈，其中保存了每个递归调用的状态。如果递归层数很深，堆栈可能会占用大量内存空间，从而增加程序的内存消耗。

4. 函数递归的两个必要条件

• 存在限制条件，当满足这个限制条件的时候，递归便不再继续。
• 每次递归调用之后越来越接近这个限制条件。

二、 函数递归实例入门

(1). 最简单的函数递归

#include<stdio.h> int main() { 
      printf("Hello World!\n"); main(); // main函数中再次调用main函数 return 0; } 

1.1 栈溢出的原因

1. 函数递归栈溢出的原因是递归深度过大，或者没有正确的递归终止条件，导致递归函数无法停止调用，不断地将新的函数压入栈中，最终导致栈空间耗尽。 就以上面所示代码为例，每调用一次main函数都会向内存申请一块空间，每调用一次就申请一次，栈中保存的数据量将会越来越大，栈空间也会被占满。当栈空间耗尽时，程序就会因为无法继续压入新的栈帧而抛出“栈溢出”异常。
2. 另一种常见的导致递归栈溢出的原因是没有正确的递归终止条件。如果递归函数没有满足退出递归的条件，那么它将会无限地调用自身，不断地将新的函数压入栈中，最终导致栈空间耗尽。这个问题可以通过在递归函数中添加终止条件来解决。

(2). 顺序打印整数的每一位

题目需求：输入一个整数m，按照顺序打印整数的每一位。

题目分析
这种输入输出数字的题，我们一定要想到取模和取余的方法,并且要有限制条件，每次函数递归后，都会越来越接近这个值。所以先函数递推1234%10=4, 123%10=3, 12%10=2, 1%10=1,给定限制条件n>9,直到n=1，打印出1，最后函数回归打印出1234。

代码实现

#include<stdio.h> void Print(int n) { 
      if (n > 9) // 限定条件 { 
      Print(n / 10); // 取模 } printf("%d ", n % 10); // 取余 } int main() { 
      int n = 0; scanf("%d", &n); Print(n); return 0; } 

画图推演

三、函数递归举例

举例1：求n的阶乘

一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，并且0的阶乘为1。⾃然数n的阶乘写作n!。

题目：计算n的阶乘（不考虑溢出），n的阶乘就是1~n的数字累积相乘。

题目分析
我们知道n的阶乘的公式： n！ = n ∗ (n − 1)!

举例： 5! = 5*4*3*2*1 4! = 4*3*2*1 所以:5! = 5*4! 

代码实现

#include<stdio.h> int Fact(int n) { 
       if (n == 0) { 
       return 1; } else { 
       return n * Fact(n - 1); } } int main() { 
       int n = 0; scanf("%d", &n); int ret = Fact(n); printf("%d\n", ret); return 0; } 

举例2：递归实现n的k次方

题目：编写一个函数实现n的k次方，使用递归实现。

题目分析

以k>0和k=0为限制条件，每一次递推就乘以n，并且k都减一次1，直到不满足限定条件，然后回归。

• 确定递归函数的参数：递归函数需要接受两个参数，分别是底数n和指数k。
• 定义递归基：当指数k等于0时，任何数的0次方都等于1，所以可以将此作为递归基，直接返回1。
• 定义递归的处理过程：递归步骤是将问题分解为计算n的k-1次方，并乘以n的结果。
• 返回结果：将递归得到的结果返回。

代码实现

#include<stdio.h> int Power(int n, int k) { 
       if (k == 1) return n; else return n * Power(n, k - 1); } int main() { 
       int ret = Power(2, 3); printf("%d\n", ret); return 0; } 

画图推演

举例3：计算一个数的每位之和（递归实现）

题目：

写一个递归函数DigitSum(n)，输入一个非负整数，返回组成它的数字之和
例如，调用DigitSum(1729)，则应该返回1+7+2+9，它的和是19
输入：1729，输出：19

题目分析

• 确定递归函数的参数：递归函数需要接受一个整数n作为参数。
• 定义递归基：当输入的整数n小于10时，即只有一位数时，直接返回该数字作为结果。
• 定义递归的处理过程：通过递归调用函数，将问题分解为计算n的最后一位数字和剩余数字之和的结果。
• 返回结果：将递归得到的结果返回。

代码实现

#include<stdio.h> int DigitSum(int n) { 
       if (n < 10) { 
       return n; } return n % 10 + DigitSum(n / 10); } int main() { 
       int n = 0; scanf("%d", &n); int ret = DigitSum(n); printf("%d\n", ret); return 0; } 

画图推演

举例4：斐波那契数（递归实现和非递归实现）

斐波那契数：斐波那契数列的第1项是1，第2项也是1。从第3项开始，每一项都等于前两项之和。

题目：
计算斐波那契数递归实现求第n个斐波那契数
例如：
输入：5 输出：5
输入：10， 输出：55
输入：2， 输出：1

(1). 递归的实现

题目分析：
斐波那系数是前两项加起来等于后一项：1，1，2，3，5，8，13…,所以我们可以以n<=2为限制条件，当n=1或2时，返回1，然后到n=3项时就是n=1项和n=2项之和，然后依次往后推，即Fib(n)=Fib(n-1)和Fib(n-2)之和。

代码实现

#include<stdio.h> int Fib(int n) { 
       if (n <= 2) return 1; else return Fib(n - 1) + Fib(n - 2); } int main() { 
       int n = 0; scanf("%d", &n); int ret = Fib(n); printf("%d", ret); return 0; } 

(2). 非递归的实现

题目分析：
也可以参考上面递归实现的思路，我们可以用三个变量相互替换来解决，n1为第一项，n2为第二项，c为第三项，运用while()循环，每一次循环n就减1，直到n=2，最后输出c。

代码实现

#include<stdio.h> int Fib(int n) { 
       int a = 1; int b = 1; int c = 1; while (n >= 3) { 
       c = a + b; a = b; b = c; n--; } return c; } int main() { 
       int n = 0; scanf("%d", &n); int ret = Fib(n); printf("%d\n", ret); return 0; } 

• 避免了重复计算：递归方式在计算斐波那契数时存在着大量的重复计算，每次递归都会重复计算前面已经计算过的子问题。而非递归方式通过迭代的方式，从前往后按顺序计算每一项，避免了重复计算，提高了效率。
• 减少函数调用开销：递归方式需要频繁地进行函数调用，每次调用都需要保存现场、传递参数等操作，会产生额外的开销。而非递归方式只需要使用循环来进行迭代计算，减少了函数调用的开销，提高了效率。
• 节省内存空间：递归方式在递归过程中需要维护函数调用栈，消耗了额外的内存空间。而非递归方式只需要使用有限的变量来保存中间结果，不需要额外的栈空间，节省了内存空间。

用迭代的方式去实现这个代码，效率就要高出很多了。