本节概要
递归概念
递归:函数自己调用自己
控制台运行结果:
递归的思想
把一个大型问题层层转换成一个与原问题相似,但规模较小的子问题求解;直到子问题不能再被拆分,递归就结束了.--- 大事化小
递归的 递是递推的意思 归是回归的意思
递归的限制条件
例子
1.求阶乘
不考虑栈溢出,所以n不能太大,n的阶乘就是 1-n 的数字累乘
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; }
求阶乘的过程图解(以3为例),红色表示递退过程,绿色表示回归过程.
2.按顺序打印
1.Print(1234)
2.==>Print(123) + printf(4)
3.==>Print(12) + printf(3)
4.==>Print(1) + printf(2)
5.==>printf(1)
画图推演:
//按顺序打印 void Print(int n) { if (n > 9) Print(n / 10); printf("%d ", n % 10); } int main() { int n = 0; scanf("%d", &n); //1234 Print(n); return 0; }
运行结果:
在 C 语言中，如果被除数和除数都是整数，则使用除号 / 进行运算时，结果将被截断为整数，不会有小数部分。如果被除数和除数中至少有一个是浮点数，则使用除号 / 进行运算时，结果将保留小数部分。例如：
int a = 5, b = 2; float c = 5.0, d = 2.0; int result1 = a / b; // 结果为 2 float result2 = a / b; // 结果为 2.0 float result3 = c / d; // 结果为 2.5
在第一个例子中，因为被除数和除数都是整数，所以结果被截断为整数 2。而在第二个例子中，虽然使用的是整数变量，但因为将运算结果存储在浮点数变量中，所以结果被转换为浮点数 2.0。在第三个例子中，被除数和除数都是浮点数，所以结果保留小数部分，为浮点数 2.5。
递归与迭代
虽然递归很好用,但是如果递归深度太深可能会发生栈溢出的问题.
这是刚刚打印,1234的例子,我们通过函数内存中的栈区去观察,它是如何进行打印的,当执行完所有函数以后我们会发现栈区里会给每一个执行完的函数开辟一个空间,直到函数执行完以后,这些空间才会被一个一个的释放出来.
如果这个打印数字很大,比如说 n = 10000 栈的内存没有那么大,就会导致在后面继续开辟内存空间的时候,栈区没有足够的空间提供给函数进行栈帧开辟,就会发生栈溢出(stack over flow)的现象
void test(int n) { if (n <= 10000) { printf("%d\n", n); test(n + 1); } } int main() { test(1); return 0; }
递归层次过深,发生栈溢出现象
迭代: 表示一种重复做的事情,循环是一种迭代
我们可以通过迭代(循环)解决阶乘问题
int main() { int n = 0; scanf("%d", &n); int i = 0; int ret = 1; for (i = 1; i <= n; i++) { ret *= i; } printf("%d\n", ret); return 0; }
运行结果:
例子
1.求第n个斐波那契数
斐波那契数列: 1 1 2 3 5 8 13 21 34 55
利用递归求
//求第n个斐波那契数 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个斐波那契数 int count = 0; int Fib(int n) { if (n == 3) count++; 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); printf("count = %d\n", count); return 0; }
利用迭代求
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; } int main() { int n = 0; scanf("%d", &n); int ret = Fib(n); printf("%d\n", ret); //printf("count = %d\n", count); return 0; }
运行结果:
Summary
1.如果一个问题使用 递归方法 写代码, 是非常方便的,简单的
写出的代码是没有明显缺陷的,这时候使用递归即可
2.如果使用递归写的代码,是存在明显缺陷的
比如:栈溢出,效率低下等
这时候必须考虑其他方式,比如: 迭代
预告
1.汉诺塔问题
相传在古印度圣庙中，有一种被称为汉诺塔的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘。 游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。
2.青蛙跳台阶问题
有一只青蛙，一次可以跳一个台阶，也可跳2个台阶如果有n个台阶，这只青蛙有多少种跳法，跳上n个台阶
