C语言：函数递归详解（建议收藏）
文章目录
- 一.基础概念
- 1.1函数递归的定义
- 1.2函数递归的优缺点
- 1.3函数递归的两个必要条件
- 二. 入门级函数递归例题
- 2.1函数递归之死循环
- 2.2输入输出1234
- 三. 函数递归典型例题的实现
- 3.1求n的阶乘
- 3.2strlen函数的模拟实现
- 3.3求n的k次幂
- 3.4字符串逆序
- 3.5斐波那契数（递归实现和非递归实现）
- 3.5.1递归的实现
- 3.5.2非递归的实现
- 3.5.3斐波那契数的非递归的实现优于递归实现的原因
- 3.6经典问题之《青蛙跳台阶》
- 3.7经典问题之《汉诺塔问题》
- 过程演示
一.基础概念
1.1函数递归的定义
程序调用自身的编程技巧称为递归（ recursion）。
递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接
调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。
1.2函数递归的优缺点
优点：函数递归只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的主要思考方式在于：把大事化小（这种思考方式十分重要）。
缺点：①如果函数递归使用不恰当，会导致栈溢出，因为每一次函数调用都会在栈区上申请内存空间。②每一次函数递归（函数调用）都会在函数栈帧上开辟一块空间，所谓的压栈。这样会大大降低我们代码的执行效率（这会在函数递归例题详解：斐波那系数中解释）。
1.3函数递归的两个必要条件
- 存在限制条件，当满足这个限制条件的时候，递归便不再继续。
- 每次递归调用之后越来越接近这个限制条件。
二. 入门级函数递归例题
2.1函数递归之死循环
我们了解了函数递归的基础概念后，来看看这段有趣而危险的代码。
#include int main() { printf("cc\n"); main(); //重复调用main函数 return 0; }可想而知，程序最终会崩溃。因为每一次函数调用都会在栈上开辟一块空间，这种死循环的代码会一直开辟空间，直至栈溢出，正如上面的缺点②。
2.2输入输出1234
题目描述:
接受一个整型值（无符号），按照顺序打印它的每一位。
例如：
输入：1234，输出 1234
解题思路：这种输入输出数字的题，我们一定要想到取模和取余的方法,并且要有限制条件，每次函数递归后，都会越来越接近这个值。
所以先函数递推1234%10=4,123%10=3,12%10=2,1%10=1，给定限制条件n>9,直到n=1，打印出最后值（1），最后函数回归打印出1234。
设n为1234
print(1234/10) + 1234%10 (=4)
print(123/10) + 123%10（=3）
print(12/10) + 12%10（=2）
当n最后为1时，不满足我们给定的限制条件n>9时，即打印1%10（=1）
代码实现：
void print(unsigned int n) { if (n > 9) //限定条件 { print(n / 10); //取模 } printf("%d ", n % 10); //取余 } int main() { unsigned int n = 0; scanf("%u",&n); //按顺序打印1234 print(n); return 0; }
三. 函数递归典型例题的实现
3.1求n的阶乘
题目描述:
用递归的方法求n的阶乘（不考虑溢出问题）
例如：
输入：4，输出 24
解题思路：n的阶乘为1234…(n-1)n，我们可以先用递推的思想，先算出n(n-1)的值，再用n(n-1)的值乘以(n-2),这样依次乘下去，以n=1为限制条件，返回1。然后再用回归思想，返回回去，及可得到n的阶乘。
JC(n)
n * JC(n-1)
n * JC(n-1) * JC(n-2)
n * JC(n-1) * JC(n-2) * JC(n-3)
…
n * JC(n-1) * JC(n-2) * JC(n-3)…JC(1)
当满足我们的限制条件n=1时，返回1，然后回归
代码实现：
int JC (int n) { if (n == 1) return 1; else return n * JC(n - 1); //阶乘的递归实现方式 } int main() { int n = 0; scanf("%d", &n); int ret = JC(n); printf("n的阶乘为：%d", ret); return 0; }
3.2strlen函数的模拟实现
题目描述:
用递归的方法模拟实现strlen函数
例如：
输入：abc，输出 3
解题思路：strlen函数遇到’\0’才会停止，所以我们以’\0’为限制条件，我们每调用一次我们自己实现的my_strlen函数，次数就加一，直到遇到’\0’停止。
my_strlen(abc)--------------这里是指针在移动
1+my_strlen(bc)
1+my_strlen(b)
1+my_strlen(‘\0’)
当满足我们的**限制条件’\0’**时，返回0，然后回归
代码实现：
int my_strlen(char* str) { if (*str != '\0') { return 1 + my_strlen(str + 1); //strlen函数的模拟实现方式 } return 0; } int main() { char arr[] = "abc"; int ret = my_strlen(arr); printf("%d", ret); return 0; }
3.3求n的k次幂
题目描述:
用递归的方法实现n的k次幂
例如：
输入：3,3，输出 27
解题思路：以k>0和k=0为限制条件，每一次递推就乘以n，并且k都减一次1，直到不满足限定条件，然后回归，即为27。
n=3,k=3
Pow(n,3)
n * Pow(n,3-1)
n * Pow(n,2-1)
n * Pow(n,1-1)
以k>0和k=0为限制条件，当k=0时，直接返回1，然后回归
代码实现：
double Pow(int n, int k) { if (k > 0) return n * Pow(n, k - 1); //① else if (k == 0) return 1; else return 1.0 / Pow(n, -k); //k是负数的时候---------------可以去步骤①,因为k大于零了 } int main() { int k = 0; int n = 0; scanf("%d %d", &n,&k); double ret = Pow(n, k); printf("%.1lf\n", ret); return 0; }
3.4字符串逆序
题目描述:
用递归的方法实现字符串逆序
例如：
输入：abcdef，输出 fedcba
解题思路：这题我们要以字符串长度为限制条件，先用临时变量tmp把a存起来，然后把f赋值给a,再把f置为’\0’（便于之后用strlen函数求字符串长度），每一次递推后面都要带有把tmp赋值给’\0’。之后再用临时变量tmp把存b起来,然后把e赋值给b,再把e置为’\0’…依次递推，直到字符串长度不大于1**时，回归回去，即可得到fedcba。
递推：
f b c d e \0
f e c d \0 \0
f e d \0 \0 \0
回归：
f e d c \0 \0
f e d c b \0
f e d c b a
代码实现：
void reverse_string(char* string) { int len = strlen(string); char tmp = *string; *string = *(string + len - 1); *(string + len - 1) = '\0'; if(strlen(string+1) > 1 ) reverse_string(string + 1); *(string + len - 1) = tmp; //这一步才能赋值，把tmp 赋值为'\0' } int main() { char arr[] = "abcdef"; reverse_string(arr); return 0; }
3.5斐波那契数（递归实现和非递归实现）
3.5.1递归的实现
题目描述:
计算斐波那契数递归实现求第n个斐波那契数
例如：
输入：5 输出：5
输入：10， 输出：55
输入：2， 输出：1
解题思路：斐波那系数是前两项加起来等于后一项：1，1，2，3，5，8，13…,所以我们可以以n if (n int n = 0; scanf("%d",&n); long ret = Fib(n); printf("%ld", ret); return 0; } int n = 0; scanf("%d",&n); int i = 0; int n1 = 1; int n2 = 1; long tmp = 0; if (n == 1) printf("%d", 1); if (n == 2) printf("%d", 1); while (n2) { tmp = n1 + n2; //三项互相替换 n1 = n2; n2 = tmp; n--; } printf("%1d", tmp); return 0; } if (n ==1) return 1; if (n ==2) return 2; else return walk(n-1) + walk(n-2); //前两项加起来等于后一项 } int main() { int n = 0; scanf("%d",&n); long ret = walk(n); printf("%ld", ret); return 0; } pimg src="https://img-blog.csdnimg.cn/9e9975b54f7d49d8865cf8494603a3bd.jpeg" height="300" //ppimg src="https://img-blog.csdnimg.cn/3732203f0c124c90a0493e5f30e2117b.jpeg" height="300" //p h33.7经典问题之《汉诺塔问题》/h3 p题目描述:/p blockquote p总共有三个柱子，在一根柱子上，从下往上按照大小顺序摞着n片圆盘。我们需要按大小顺序重新摆放在另一根柱子上。并且规定，在移动过程，小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。/p /blockquote p解题思路：我们需要把圆盘看做一个一个的整体，而且需要有大事化小的思想。假设我们有三根柱子：A,B,C（A:表示起始位置，B:表示中转站/pp，C:表示目标位置）/p ulli如果A柱有n=1个盘子，我们只要把它移动到C柱上就可以了。对应过程演示（1）。/lili如果A柱有n=2个盘子，则需先把A柱上第一个盘子放到B柱上 -> 再把A柱上第二个盘子（这时n=1）放到C柱上。对应过程演示（2）。
- 如果A柱有n=3个盘子，①.第一步：则需先把A柱上第一个盘子放到C柱上 -> 再把A柱上第二个盘子放到B柱上 -> 然后把C柱上的盘子放到B柱上面 -> 然后把A柱上第三个盘子（这时n=1）放到C柱上。②.第二步：再想办法把B柱上的圆盘移动到A柱上,先把B柱上第一个圆盘放到A柱上 -> 再把B柱上的圆盘放到C柱上 -> 最后再把A柱上的圆盘放到C柱上。对应过程演示（3）。
- …
- 如果A柱有n个盘子，步骤是一样的，肯定是先想办法把A柱上n-1个圆盘移动到B柱上 -> 之后才能想办法把第n个圆盘从A柱放到C柱上面（即n=1的时候，递归的限制条件） -> 最后想办法把B柱上的圆盘移动到C柱上面。对应过程演示（4）。
这里递归的限制条件是n=1
并且一定要注意：我们在解决汉诺塔问题时，一定不能太过于深究里面圆盘移动的过程，因为比较复杂，很容易让人绕进去。所以我们这里不考虑上述中的“想办法”（即移动的过程）
我们只要懂其中的原理就可以把汉诺塔实现出来，运用大事化小的思想
代码实现：
void Move(char src, char dest) { // src表示的是起始位置，dest表示的是目标位置 printf("盘子从%c柱子->%c柱子\n",src,dest); } void Plate_Move(int n, char A, char B, char C) { if (n == 1) { Move(A, C); //这里即递归停下来的地方，把最底下一层的盘子（n），移动到C柱上 } else //这里下面都是在递归ing!!! （下面这三条语句其实都是在同步进行的） { Plate_Move(n-1,A,C,B);//当不只一个圆盘时，我们先将上面 （n -1）个圆盘 借助 C柱子 从 A 柱子移动到 B 柱子 Move(A, C); //A柱剩余一个圆盘，将剩下的一个圆盘从 A 移动到 C Plate_Move(n - 1, B, A, C); //以A柱为中转站，把B柱上的圆盘放在C上。 } } int main() { int n = 0; scanf("%d", &n); Plate_Move(n, 'A', 'B', 'C'); //n为几个圆盘，A,B,C分别对应A，B，C三个柱子 return 0; }过程演示
（1）A柱上有1个圆盘：
（2）A柱上有2个圆盘：
（3）A柱上有3个圆盘：
（4）A柱上有n个圆盘：
- 过程演示
