C语言--函数递归

目录

1、什么是递归？

1.1 递归的思想

1.2 递归的限制条件

2. 递归举例

2.1 举例1：求n的阶乘

2.2 举例2：顺序打印⼀个整数的每⼀位

 3. 递归与迭代

扩展学习：

---

早上好，下午好，晚上好

1、什么是递归？
 

递归其实是⼀种解决问题的⽅法，在C语⾔中，递归就是函数 ⾃⼰调⽤⾃⼰ 。 写⼀个史上最简单的C语⾔递归代码：

#include <stdio.h>int main(){ printf("hehe\n"); main();//main函数中⼜调⽤了main函数 return 0;}

上述就是⼀个简单的递归程序，只不过上⾯的递归只是为了演⽰递归的基本形式，不是为了解决问 题，代码最终也会陷⼊死递归，导致栈溢出

1.1 递归的思想

把⼀个⼤型复杂问题层层转化为⼀个与原问题相似，但规模较⼩的⼦问题来求解；直到⼦问题不能再 被拆分，递归就结束了。所以递归的思考⽅式就是把⼤事化⼩的过程。 递归中的 递就是递推 的意思， 归就是回归 的意思

1.2 递归的限制条件

递归在书写的时候，有2个必要条件： • 递归存在 限制条件 ，当满⾜这个限制条件的时候，递归便不再继续。 • 每次递归调⽤之后 越来越接近 这个限制条件

2. 递归举例

2.1 举例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!

这样的思路就是把⼀个较⼤的问题，转换为⼀个与原问题相似，但 规模较⼩ 的问题来求解的。 当 n==0 的时候，n的阶乘是1，其余n的阶乘都是可以通过公式计算。 n的阶乘的递归公式如下：

 

 

那我们就可以写出函数 Fact求n的阶乘 ，假设 Fact(n)就是求n的阶乘 ，那么 Fact(n-1)就是求n-1 的阶 乘，如下：

#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.2 举例2：顺序打印⼀个整数的每⼀位

输⼊⼀个整数m，按照顺序打印整数的每⼀位。 比如： 输⼊：1234 输出：1 2 3 4 输⼊：520 输出：5 2 0

 

1234%10就能得到4，然后1234/10得到123，这就相当于去掉了4 然后继续对123%10，就得到了3，再除10去掉3，以此类推 不断的 %10 和 /10 操作，直到1234的每⼀位都得到 但是这⾥有个问题就是得到的数字顺序是倒着的 但是我们有了灵感，发现其实⼀个数字的最低位是最容易得到的，通过%10就能得到 那我们假设想写⼀个函数Print来打印n的每⼀位，如下表⽰：

Print(n)如果n是1234，那表⽰为Print(1234) //打印1234的每⼀位其中1234中的4可以通过%10得到，那么Print(1234)就可以拆分为两步：1. Print(1234/10) //打印123的每⼀位2. printf(1234%10) //打印4完成上述2步，那就完成了1234每⼀位的打印那么Print(123)⼜可以拆分为Print(123/10) + printf(123%10)

以此类推下去，就有

Print(1234)==>Print(123) + printf(4)==>Print(12) + printf(3)==>Print(1) + printf(2)==>printf(1)

直到被打印的数字变成⼀位数的时候，就不需要再拆分，递归结束。

void Print(int n){ if(n>9) { Print(n/10); } printf("%d ", n%10);}int main(){ int m = 0; scanf("%d", &m); Print(m); return 0;}

在这个解题的过程中，我们就是使⽤了⼤事化⼩的思路 把Print(1234) 打印1234每⼀位， 拆解为 ⾸先 Print(123) 打印123的每⼀位，再打印得到的4 把Print(123) 打印123每⼀位，拆解为⾸先 Print(12) 打印12的每⼀位，再打印得到的3 直到Print打印的是 ⼀位数 ，直接打印就⾏。 画图推演:

 3. 递归与迭代

递归是⼀种很好的编程技巧，但是和很多技巧⼀样，也是可能被误⽤的 在C语⾔中每⼀次函数调⽤，都要需要为本次函数调⽤在栈区 申请⼀块内存空间 来保存函数调⽤期间的各种局部变量的值，这块空间被称为 运⾏时堆栈 ，或者 函数栈帧 。 函数不返回，函数对应的栈帧空间就 ⼀直占⽤ ，所以如果函数调⽤中存在递归调⽤的话，每⼀次递归函数调⽤都会开辟属于⾃⼰的栈帧空间，直到函数递归不再继续，开始回归，才逐层释放栈帧空间。 所以如果采⽤函数递归的⽅式完成代码，递归 层次太深 ，就会 浪费 太多的栈帧空间，也可能引起 栈溢出 的问题

 

所以如果不想使⽤递归就得想其他的办法，通常就是迭代的⽅式（通常就是循环的⽅式）。 ⽐如：计算n的阶乘，也是可以产⽣1~n的数字累计乘在⼀起的。

int Fact(int n){ int i = 0; int ret = 1; for(i=1; i<=n; i++) { ret *= i; } return ret;}

举例：求第n个斐波那契数 我们也能举出更加 极端的例⼦ ，就像计算第n个斐波那契数，是不适合使⽤递归求解的，但是斐波那契数的问题通过是使⽤递归的形式描述的，如下：

 

 看到这公式，很容易诱导

#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\n", ret);  return 0;}

当我们n输⼊为50的时候，需要很⻓时间才能算出结果，这个计算所花费的时间，是我们很难接受的，这也说明递归的写法是 ⾮常低效 的，那是为什么呢

 

其实递归程序会不断的展开，在展开的过程中，我们很容易就能发现，在递归的过程中会有 重复 计 算，⽽且递归层次越深， 冗余计算 就会越多。 我们知道斐波那契数的前2个数都1，然后前2个数相加就是第3个数，那么我们从前往后，从⼩到⼤计算就⾏了。 这样就有下⾯的代码：

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;}

迭代的⽅式去实现这个代码， 效率 就要⾼出很多了。 有时候，递归虽好，但是也会引⼊⼀些问题，所以我们⼀定不要迷恋递归， 适可⽽⽌ 就好。

扩展学习：

汉诺塔问题（经典递归问题）

汉诺塔问题是一个经典的问题。汉诺塔（Hanoi Tower），又称河内塔，源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。问应该如何操作？

 

 假设总共需要移动n个盘子
1.将A柱上的n-1个盘子借助C柱移向B柱
2.将A柱上仅剩的最后一个盘子移向C柱
3.将B柱上的n-1个盘子借助A柱移向C柱

#define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>void move(int x, int y){printf("%c->%c\n", x, y);}void hanoi(int n, char a, char b, char c){if (n == 1){move(a, c);}else{hanoi(n - 1, a, c, b);//将A座上的n-1个盘子借助C座移向B座move(a, c);//将A座上最后一个盘子移向C座hanoi(n - 1, b, a, c);//将B座上的n-1个盘子借助A座移向C座} }//move中的实参与hanoi函数中的形参相对应，而hanoi函数中形参a，b，c所对应的值也是在有规律的变化int main(){int n = 0;scanf("%d", &n);hanoi(n, 'A', 'B', 'C');return 0;}

 感谢观看