7. 函数递归
7.1 什么是递归？
程序调用自身的编程技巧称为递归（ recursion）。
递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接
调用自身的
一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，
递归策略
只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
递归的主要思考方式在于：把大事化小
7.2 递归的两个必要条件
存在限制条件，当满足这个限制条件的时候，递归便不再继续。
每次递归调用之后越来越接近这个限制条件。
7.2.1 练习1：（画图讲解）
接受一个整型值（无符号），按照顺序打印它的每一位。
例如：
输入：1234，输出 1 2 3 4。
//%u - 无符号的整数 //%d - 有符号的整数 // //Print(1234) //Print(123) 4 //Print(12) 3 4 //Print(1) 2 3 4 // void Print(unsigned int n) { if (n > 9) { Print(n / 10); } printf("%d ", n % 10); } int main() { unsigned int num = 0; scanf("%u", &num); Print(num); return 0; }
7.2.2 练习2：（画图讲解）
编写函数不允许创建临时变量，求字符串的长度。
求字符串的长度。
#include <stdio.h> #include <string.h> int main() { char arr[10] = "abcdef"; int len = strlen(arr); printf("%d\n", len); return 0; }
编写函数，求字符串的长度。
#include <stdio.h> #include <string.h> int my_strlen(char* str) { int count = 0; while (*str != '\0') { count++; str++; } return count; } int main() { char arr[10] = "abcdef"; int len = my_strlen(arr); printf("%d\n", len); return 0; }
编写函数不允许创建临时变量，求字符串的长度。
#include <stdio.h> #include <string.h> int my_strlen(char* str) { if (*str != '\0') return 1 + my_strlen(str+1);//加1会改变地址加1 abcdef——>bcdef else return 0; } int main() { char arr[10] = "abcdef"; int len = my_strlen(arr); printf("%d\n", len); return 0; }
图解
7.3 递归与迭代
7.3.1 练习3：
求n的阶乘。（不考虑溢出）
不考虑递归与迭代
#include <stdio.h> int fac(int n) { int i = 0; int ret = 1; for (i = 1; i <= n; i++) { ret = ret * i; } return ret; } int main() { int n = 0; scanf("%d", &n); int ret = fac(n); printf("%d\n", ret); return 0; }
考虑递归与迭代
#include <stdio.h> int fac(int n) { if (n <= 1) return 1; else return n * fac(n - 1); } int main() { int n = 0; scanf("%d", &n); int ret = fac(n); printf("%d\n", ret); return 0; }
图片详解
7.3.2 练习4：
求第n个斐波那契数。（不考虑溢出）
详细图解
运用递归的方法
//求第n个斐波那契数 #include <stdio.h> int count = 0; int Fib(int n) { //count统计的是第3个斐波那契数被重复计算的次数 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);//40 int ret = Fib(n); printf("%d\n", ret); //printf("count = %d\n", count); return 0; }
运用迭代的方法
#include <stdio.h> //迭代的方式 int Fib(int n) { int a = 1; int b = 1; int c = 1; while (n>=3) { c = a + b; a = b; b = c; n--; } return c; } int main() { int n = 0; scanf("%d", &n);//40 int ret = Fib(n); printf("%d\n", ret); //printf("count = %d\n", count); return 0; }
8. 有关斐波那契的题型
汉诺塔问题
青蛙跳台阶问题
