什么是递归
递归就是一个函数在它的函数体内调用它自身来解决问题，实现将大事化小，复杂化简单
两个基本要素
递归关系
执行递归函数，满足递归关系将反复调用其自身，每调用一次就进入新的一层（类似递推的感觉）
结束条件
如果函数一直递推，每递推一次就会开辟一个空间，而内存是有限的
就需要一个限制条件，当无法满足继续递归时，就开始返回（回归）
注：因为开辟空间，返回时调用函数中的变量依然会保持使用，以此实现反向输出得到想要的结果
递归的精髓在于通过不断地重复逼近一个最终的结果,它更多的是一种思想,用于解决某些问题
例题
按顺序打印整形数组
分析问题
举例打印1234，尝试分解问题，逼近想要的结果
一个数余10，我们可以得到个位数
想的到十位数，可以先除十再余十（整形间除法是没有小数位的）
参考代码
void print(unsigned int n) { if (n > 9) { print(n / 10);//递推关系 } printf("%d ", n % 10);//开始返回 } int main() { //接受一个整型值（无符号），按照顺序打印它的每一位 unsigned int num = 0; scanf("%u", &num);//1234 print(num); return 0; }
这样看来递归还是非常有意思的哈
求字符串的长度（编写函数不允许创建临时变量）
分析问题
找到递归关系：想特点，字符串是以‘\0’结尾的
参考代码
int my_strlen(char* s) { if (*s != '\0') { return 1 + my_strlen(s+1); } else { return 0; } } int main() { //求字符串长度 char arr[10] = "abcd"; //数组名arr是数组首元素的地址 - char* int len = my_strlen(arr);//6 printf("%d\n", len); return 0; }
再来，来试试思考下面这个问题
求n的阶乘
分析问题如何逼近结果，思考两个要素
参考代码
int Fac(int n) { if (n <= 1) return 1; else return n* Fac(n - 1); } int main() { int n = 0; scanf("%d", &n);//3 //去n的阶乘 int ret = Fac(n); printf("%d\n", ret); return 0; }
递归这样看来十分快捷简便，但它也有局限，毕竟递归是一个不断调用函数重复的过程
斐波那契数列
0, 1, 1, 2, 3, 5, 8, 13, 21, ···
斐波那契数列是一个从第三项开始,每一项都等于前两项之和的数列问题
函数化思想如下
int count = 0; int Fib1(int n) { if (n == 3) { count++; } if (n <= 2) return 1; else return Fib1(n - 1) + Fib1(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; }
仅从求第五项来看，就调用了4次第一项
想想那第五十项，又要调用多少次，计算有需要多久呢？(存在明显问题)
而用循环对于这个问题却又变得简单许多，至少计算很快
//迭代(循环) 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; }
总结特点
优点
1. 简洁
2.在树的前序，中序，后序遍历算法中，递归的实现明显要比循环简单得多。
缺点
1.递归由于是函数调用自身，而函数调用是有时间和空间的消耗的：每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址以及临时变量，而往栈中压入数据和弹出数据都需要时间。->效率
2.递归中很多计算都是重复的，由于其本质是把一个问题分解成两个或者多个小问题，多个小问题存在相互重叠的部分，则存在重复计算，如fibonacci斐波那契数列的递归实现。->效率
3.调用栈可能会溢出，其实每一次函数调用会在内存栈中分配空间，而每个进程的栈的容量是有限的，当调用的层次太多时，就会超出栈的容量，从而导致栈溢出。->性能
什么时候使用
