一、什么是递归？
1、初中数学题 -- 根据数字找规律:
1,1,2,3,5,8,( ),21... 求括号中的数字？
通过从左到右观察，我们可以看出，从第 2 个数开始，后一个数等于前两个数之和。
2 = 1 + 1；3 = 2 + 1；5 = 3 + 2；8 = 5 + 3；
可以得出括号内的数为 5 + 8 = 13。
这是一个斐波那契数列，也是一个典型的递归数列。
我们可以得出一个表达式：
F (1) = 1，
F (2) = 1,
F (n) = F (n-1) + F (n-2)（n>=3，n∈N*）
2、如何理解 “递归”？
① 两个必要条件
● 递归条件
“递归条件”指的是自己调用自己，比如 F (n) = F (n-1) + F (n-2)
● 基线条件
在递归终止条件，不再调用自己，从而比避免进入死循环
② 递归代码
Python代码
输出结果
③ 总结
写递归代码的关键就是找到如何将大问题分解为小问题，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。
二、递归的优缺点
1、优点
● 代码的表达力强，书写简洁。
2、缺点
● 递归会利用栈保存临时变量，如果递归过深，会造成栈溢出。
解决方案是控制递归的深度。
● 存在重复计算、过多的函数调用会耗时较多等问题
斐波那契数列递归求 fn(6)
图
从上图中可看出，会进行重复计算
三、递归函数转换为非递归函数
四、建议
递归代码虽然简洁高效，但是，递归代码也有很多弊端。比如，堆栈溢出、重复计算、函数调用耗时多、空间复杂度高等，所以，在编写递归代码的时候，一定要控制好这些副作用。
>>>