引言
递归函数同java一样，也是函数本身调用自己，从而实现类似循环的效果
示例
举个例子，我们来计算阶乘n! = 1 x 2 x 3 x ... x n，这个问题的解决方法其实可以用循环来实现，即从0循环遍历到n，计算所有数的乘积
def cal(n):
result=1
if isinstance(n,int)：
i=1
while(i<n):
result=result*i
i=i+1
return result
用循环来说可以实现，那么怎么用递归呢？
我们来分析一下
我们定义的这个fact函数功能
- 检验传入的参数是否是整数 int 类型
- 检验传入的参数是否大于等于1
- 检验通过后，会进行循环乘法运算
- 返回结果
那么其实只要输入成立，那么会一直执行乘法运算
比如我们计算1234...*10
那么其实可以拆分来看
1234...*10即为10!
那么
10!=9!10
9!=8!9
8!=7!8
.
.
.
2!=1!2
1!=1
那么抽象一下就是
n!=(n-1)!n=((n-2)!(n-1))*n=...一直抽取出来知道抽取到1!
=(1!(n-(n-2)))(n-3)(n-4)....n
感觉是不是越来越乱？
那么我换句话说就是 其实一直在做相似的操作：即一直做：前一个数的阶乘 * 自己
即 (n-1)!*n
最后只不过把这些东西抽到了最后而已
好了 ，我们不绕弯子了，直接上代码吧
def fact(n):
result=1
if not (isinstance(n) and n<=0):
raise TypeError('bad type')
elif n==1:
result=1
else:
result=fact(n-1)*n
return result
调用一下看看
fact(1)
fact(2)
fact(5)
结果输出正确
1
2
120
看实际示例
是不是这样写，比循环省很多事呢？
存在的问题
上图中，我计算100!输出了结果
但是计算1000!却报错了
报错原因：
result=fact(n-1)*n
[Previous line repeated 994 more times]
File "./fact.py", line 4, in fact
if not (isinstance(n,int) and n>=1):
RecursionError: maximum recursion depth exceeded in comparison
执行的次数太多
导致「栈溢出」
栈溢出？
在计算机中，python的函数调用是通过 stack(栈)这种数据结构实现的，每进入一个函数调用，栈内就会增加一个栈帧，每当函数返回，栈就会减少一个栈帧，而栈的空间是由计算机和开发环境决定的，所以栈的空间是有限的，所以刚才我们的递归调用次数过多（递归中一直没有做递归函数的返回），故导致栈溢出
怎么解决呢？
解决递归调用栈溢出的方法是通过
尾递归优化
尾递归和循环的效果是一样的，所以，把循环看成是一种特殊的尾递归函数也是可以的。
什么是尾递归呢？
尾递归的意思是：在函数返回时，调用函数本身，并且 return语句不能包含表达式，必须是函数本身才可以。
这样函数在调用的时候，在计算机中只占用一个「栈帧」，就不会出现「栈溢出」的现象了。
我们上方的函数怎么改成「尾递归」呢
def fact(n,result):
if not (isinstance(n,int) and n>=1):
raise TypeError('bad type')
elif n==1:
return result
else return fact(n-1,result*n)
其实就是将我们之前的运算结果放入到了函数的参数中，直接然后遍历到1的时候，直接返回
不过，我们调用的时候需要这么调用
fact(n,1)
因为第二个参数 其实是当「递归」结束时候的返回的数值
而「递归」结束时，就是回到了1，那么1的「阶乘」就是1，所以第二个参数是1
看下示例代码：
不过，遗憾的是，大多数编程语言没有针对尾递归做优化，Python解释器也没有做优化，所以，即使把上面的fact(n)函数改成尾递归方式，也会导致栈溢出。
所以还是会出现：
总结
其实 python的遍历和其他语言没什么区别，其中要注意的是当我们用的时候，最好使用「尾递归」去实现
