8.函数递归（难使用，会导致栈溢出）：
8.1 什么是递归：
程序调用自身的编程技巧称为递归（recurion）。
递归作为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
递归的主要思考方式在于：把大事化小
（递归和循环类似，但递归每次都要开辟空间，而循环每次都是使用固定的数据，所以循环不会让程序崩溃，而递归可能会让程序崩溃）
8.2 递归的两个必要条件：
- 存在限制条件，当满足这个限制条件的时候，递归便不再继续。
- 每次递归调用之后越来越接近这个限制条件。
（两个条件有了不一定对，没了一定错。）
(以下面练习1为例：)
[不满足这两个条件的情况下，易导致 栈溢出(Stack overflow) ]
//递归 #include <stdio.h> int main() { printf("hehe\n"); // 递归：函数自己调用自己 main(); return 0; }
8.2.1 练习1：（画图理解）
接受一个整型值（无符号），按照顺序打印它的每一位
例如：
输入：1234 ； 输出：1 2 3 4
（画图理解：）
递归的 递 理解为 递推 会好些）
//递归 练习1： #include <stdio.h> void print(unsigned int n) // 1234 { if (n > 9) // 大于9说明是两位数 { print(n / 10); // 1234进来后变为123 } printf("%d ", n % 10); // } int main() { unsigned int num = 0; //输入 scanf("%d", &num); print(num); // 调用自定义函数 return 0; }
（递归过程涉及 函数的调用堆栈 ，也叫 函数栈帧 。）
补充：函数的调用堆栈（函数栈帧）
（下篇再进行详细补充）
[每一次函数调用都要创造函数栈帧，整个函数栈帧的空间都在栈区上（函数栈帧的开辟都是在栈区上进行的）]
8.2.1 练习2：（画图理解）
编写函数不允许创建临时变量，求字符串的长度。
（使用临时变量的解法：）
//编写函数不允许创建临时变量，求字符串的长度 #include <stdio.h> #include <string.h> int my_strlen(char* s) // 返回字符串长度，所以返回类型是int // 因为实参是数组名称，是地址，所以形参使用 char* // 数组末尾包括 \0 , 求字符串长度是求 \0 前有多少个字符（注意） { int count = 0; // 临时变量 while (*s != '\0') // 如果没有到\0（结束标志）,说明数组还有值，就继续循环 // 使用 s指针 往后遍历字符串 ，字符串放在数组中是连续的 { count++; // 加入循环说明有值，计数加1 s++; // 让指针往后偏移，判断下一位 } return count; } int main() { char arr[] = "abc"; // 这个数组相当于 {a b c \0] int len = my_strlen(arr); // 调用自定义函数 printf("%d\n", len); // 字符数组的数组名是首元素的地址 return 0; }
（无临时变量解法：）
// 使用递归 // my_strlen("abc") --> 1 + my_strlen("bc") // --> 1 + 1 + my_strlen("c") --> 1 + 1 + 1 + my_strlen("\0") // --> 1 + 1 + 1 + 0 (\0 不计数 ，记为0) // -> 把字符一个一个剥离下来（大事化小） int my_strlen(char* s) { if (*s == '\0') { return 0; // 首地址数为\0,说明为空数组 } else { // 进入else说明首地址有值，所以先给个1 return 1 + my_strlen(s + 1); // 使用递归 // (s + 1)相当于让指针往后偏移，判断下一位 } } int main() { char arr[] = "abc"; // 这个数组相当于 {a b c \0] int len = my_strlen(arr); // 调用自定义函数 printf("%d\n", len); // 字符数组的数组名是首元素的地址 return 0; }
8.3 递归与迭代（循环就是一种迭代）：
许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。
但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。
当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销。
8.3.1 练习3：
求n的阶乘。（不考虑溢出）
（使用迭代解法：）
// 求n的阶乘(迭代) #include <stdio.h> // 循环（迭代） int Fac(int n) { int r = 1; int i = 0; for ( i = 1; i <= n; i++ ) // 产生1-n的数 { r = r * i; } return r; } int main() { int n = 0; scanf("%d", &n); int ret = Fac(n); // 调用自定义函数 printf("%d\n", ret); return 0; }
（使用递归解法：）
（出现函数自己调用自己，使用递归）
// 求n的阶乘(迭代) #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; }
8.3.2 练习4：
求第n个斐波那契数。（不考虑溢出）
（出现函数自己调用自己，使用递归）
// 求第n个斐波那契数 // 1 1 2 3 5 8 13 21 34 55 ... // 前2个的数的和是第三个数 #include <stdio.h> int Fib(int n) { if (n <= 2) { return 1; // 前两个斐波那契数都是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; }
（上面解法有弊端）
栈溢出：
在调试 Fib 函数的时候，如果你的参数比较大，
那就会报错： stack overflow（栈溢出） 这样的信息。
系统分配给程序的栈空间是有限的，但是如果出现了死循环，或者死递归，
这样有可能导致一直开辟栈空间，最终产生栈空间耗尽的情况，这样的现象我们称为栈溢出。
（递归反倒使计算量变多了，递推出去成千上万个分支，再回归成千上万个分支，效率太低了）
（使用迭代的解法：）
// 求第n个斐波那契数(迭代) // 1 1 2 3 5 8 13 21 34 55 ... // 前2个的数的和是第三个数 #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); int ret = Fib(n); // 调用自定义函数 printf("%d\n", ret); return 0; }
（值太大了，所以结果不对，此题是不考虑溢出）
