| C语言递归及经典例题详解 | 您所在的位置：网站首页 › 递归问题中包含哪些项 › C语言递归及经典例题详解 |
C语言递归及经典例题详解
|
什么是递归？ 什么时候使用递归 例题1 顺序打印问题 例题2 求n的阶乘 例题3 求第n个斐波那契数 经典 汉诺塔问题 经典 青蛙跳台阶问题 什么是递归？递归就是程序调用自身的编程技巧。递归通常把一个大型复杂的问题层层转化为一个与原问题相似，规模较小的问题来求解。递归策略只需要少量的程序就可以描述出解题过程所需要的多次重复的计算，大大减少程序的代码量。 递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。 什么时候使用递归？1、大问题可以拆分成若干小问题。 2、原问题与子问题除数据规模不同，求解思路完全相同。 3、存在递归终止条件。 4、当不满足终止条件时，要如何缩小函数值，并让其进入下一层循环中。 例题1 顺序打印问题：输入一个整数123，依次在屏幕打印1 2 3 代码： #include void print(int n) { if (n > 10) { print(n / 10); } printf("%d ", n%10); } int main() { int n = 0; scanf_s("%d", &n); print(n); return 0; }
例题分析：本题的思路不断拆分整数，并将他们一一打印，只要n>10,就另n不断除以10，不断的递归调用n/10，当n1时，n!=n*Fac(n-1)。我们求Fac(n)，就是不断求Fac(n-1)的过程，当不断递归求到Fac(1)时，依次计算阶乘返回，最终得到n！ 例题3 求斐波那契数列求第n个斐波那契数 代码： int Fib(int n) { if (n CA->B C->B A->C B->A B->C A->C 以上3个盘子移动共经历了7步完成。 从这里我们可以推出规律：如果有n个盘子移动，一共会经历2^n-1步。 所以如何移动n个盘子呢？ 道理和3个盘子移动是一样的，移动过程如下： 1、将A柱上的n-1个盘子移动到B柱（借助C） 2、将A柱上的一个盘子移动到C柱 3、将B柱上的n-1个盘子移动到C柱（借助A） 代码： #include void move(char x, char y) { printf("%c-->%c\n", x, y); } void hanoi(int m, char one, char two, char three) { if (m == 1) { move(one, three); } else { hanoi(m - 1, one, three, two); move(one, three); hanoi(m - 1, two, one, three); } } int main() { int m = 0; printf("请输入移动盘子的数量：>\n"); scanf_s("%d", &m); hanoi(m, 'A', 'B', 'C'); return 0; }移盘方案：
一只青蛙一次可以跳上一级台阶，也可以跳上2级，求该青蛙跳上n级的台阶总共有多少种跳法（先后次序不同算不同结果）。 例题分析：此题可以分为台阶有1，2，3....n级台阶。 台阶为1级时：有1种跳法 台阶为2级时：有2种跳法 台阶为3级时：有3种跳法 台阶为4级时：有5种跳法 ........ 台阶为n级时：有(n-1)+(n-2)种跳法 代码： int jumpFloor(int m) { if (m == 1) { return 1; } else if (m == 2) { return 2; } else { return jumpFloor(m - 1) + jumpFloor(m - 2); } } int main() { int target = 0; printf("请输入青蛙所要跳的台阶数：>\n"); scanf_s("%d", &target); int ret = jumpFloor(target); printf("%d\n", ret); return 0; }感谢阅读，欢迎大家批评指正！ |
【本文地址】