C语言函数递归

一、递归的概念与思想

二、递归的限制条件

三、递归的实际应用举例

（一）求 n 的阶乘

（二）顺序打印一个整数的每一位

四、递归与迭代的比较

五、递归的拓展应用

在 C 语言的学习旅程中，函数递归是一个既有趣又极具挑战性的概念。它为我们提供了一种独特的解决问题的思路，就像一把神奇的钥匙，能打开许多复杂问题的大门。今天，就让我们一起深入探索函数递归的世界

一、递归的概念与思想

递归，简单来说，就是函数自己调用自己。这听起来有点像在一个无限循环里打转，但实际上它有着明确的逻辑和目的。在 C 语言中，递归是一种强大的解决问题的方法，其核心思想是把一个大型复杂问题层层转化为一个与原问题相似，但规模较小的子问题来求解。直到子问题不能再被拆分，递归就结束了，这就是把大事化小的过程。

我们来看一个简单的示例代码：
#include <stdio.h>
int main()
{printf("hehe\n");main();//main函数中又调用了main函数return 0;
}
这段代码展示了递归的基本形式，但它只是为了演示，并非用于实际解决问题。由于没有设置限制条件，它会陷入死递归，最终导致栈溢出（Stack overflow）。就好比一个人在一条没有尽头的走廊里一直往前走，永远也走不出去，最后精疲力竭。

二、递归的限制条件

为了避免递归陷入死循环，我们在使用递归时必须遵循两个必要条件：

存在限制条件：当满足这个限制条件的时候，递归便不再继续。这个限制条件就像是给递归设定了一个终点，告诉它什么时候该停下来。
每次递归调用之后越来越接近这个限制条件：这确保了递归能够逐步收敛，最终达到限制条件，结束递归过程。

三、递归的实际应用举例

（一）求 n 的阶乘

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

根据这个公式，我们可以编写如下函数来计算 n 的阶乘：
int Fact(int n)
{if(n==0)return 1;elsereturn n*Fact(n-1);
}
在这个函数中，当 n 等于 0 时，递归结束，返回 1；否则，继续调用 Fact 函数，将问题规模逐渐缩小，直到 n 为 0。

测试代码：（这⾥不考虑n太⼤的情况，n太大存在溢出）

栈溢出指的是当程序在栈上不断分配内存，使得栈的使用空间超出了预先分配的最大容量，就会发生栈溢出错误。这就好像一个容量有限的容器，不断往里面装东西，最终东西多得装不下了。

递归函数在调用自身时，每一次调用都会在栈上创建一个新的栈帧。如果递归没有合理的终止条件，或者递归深度过大，栈空间就会不断被占用，最终导致栈溢出。

（二）顺序打印一个整数的每一位

输入一个整数 m，按照顺序打印整数的每一位。例如，输入 1234，输出 1 2 3 4 。我们可以通过 %10 和 / 10 操作来拆分整数的每一位。假设想写一个函数 Print 来打印 n 的每一位，其实现思路如下：
void Print(int n)
{if(n>9){Print(n/10);}printf("%d ", n%10);
}
在这个函数中，如果 n 大于 9，就继续调用 Print 函数处理 n/10，直到 n 为一位数，然后打印 n%10。这样就实现了顺序打印整数的每一位。

四、递归与迭代的比较

递归虽然是一种强大的编程技巧，但它也有自己的局限性。在递归函数调用的过程中，每一次函数调用都需要在内存的栈区申请一块内存空间来保存函数调用期间的各种局部变量的值，这块空间被称为运行时堆栈或函数栈帧。如果递归层次太深，就会浪费太多的栈帧空间，甚至可能引起栈溢出的问题。

相比之下，迭代（通常就是循环的方式）在很多情况下效率更高。以计算 n 的阶乘为例，使用迭代方式的代码如下：
int Fact(int n)
{int i = 0;int ret = 1;for(i=1; i<=n; i++){ret *= i;}return ret;
}
这段代码通过循环实现了与递归相同的功能，而且效率更高。因为它不需要频繁地开辟和释放栈帧空间

再比如计算第 n 个斐波那契数，斐波那契数列的递归公式为：

按照这个公式编写的递归代码在计算较大的 n 时效率极低，因为会产生大量的重复计算。例如，在计算第 40 个斐波那契数时，第 3 个斐波那契数就被重复计算了 39088169 次。而使用迭代方式可以大大提高效率：
int Fib(int n)
{int a = 1;int b = 1;int c = 1;while(n>2){c = a+b;a = b;b = c;n--;}return c;
}

五、递归的拓展应用

斐波那契数列的特点是前两个数为 1，从第三个数开始，每个数都等于前两个数之和。用递归方式计算第n个斐波那契数的代码如下：
int Fib(int n)
{ if(n==0)return 0;if(n==1)return 1;elsereturn Fib(n-1)+Fib(n-2);
}
然而，当n较大时，如n=50，使用这种递归方式计算会花费极长的时间，因为递归过程中存在大量重复计算。为了优化，可以采用迭代方式:
int Fib(int n)
{   int a = 1;int b =1;int c= 1;while(n>2){ C= atb;a =b;n--j}return c;
}
迭代方式从前往后依次计算斐波那契数，避免了重复计算，大大提高了效率

青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2 级台阶，求青蛙跳上n级台阶总共有多少种跳法。这是一个可以用递归很好解决的问题。假设跳上n级台阶的跳法数为F(n)，则有F(N) = F(N-1)+F(N-2) ,这与悲波那韧数列的递归公式相似。当n为1时，只有1种跳法;当n为2时，有2种跳法(一次跳2级或分两次每次跳1级)。递归实现代码如下:
int FrogJump(int n)
{if(n == 1)return 1;if(n == 2)return 2;return FrogJump(n-1)+FrogJump(n-2);
}
同样，为了提高效率，也可以将其转换为迭代实现。

汉诺塔问题是一个古老的益智游戏，有三根柱子 A、B、C，A 柱上有若干个盘子，盘子大小不等，大的在下，小的在上。要求将 A柱上的盘子借助 B柱全部移到C柱上，每次只能移动日在移动讨程中大母子不能前在小盘子上面。这个问题可以用递归完美解决。假设要将n个盘子从 A 柱借助 B 柱移到 C 柱递归思路如下: