1.递归 递归就是函数出现了自己调用自己的情况。

例如： 求斐波那契数列的第n项。 什么是斐波那契数列？数列的前两项都是1，从第三项开始每一项是前两项之和，这样的数列称为斐波那契数列。 例如： 1,1,2,3,5,8,13…这样一个数列就是斐波那契数列。 求斐波那契数列第n项的值，就可以使用递归实现。

# -*- coding: utf-8 -*-
# @Time : 2022/3/28 11:03
# @File : function7.py
# @Software : PyCharm

def fact(n):
    if(n==1 or n==2):
        return 1
    return fact(n-1)+fact(n-2)

result = fact(10)
print(result)

运行结果：

55

以上代码看似没有问题，可是当我们把n取值稍大些，比如；n=100, 运行时接近死机状态，几乎无法得到结果。之所以出现这样的情形，是因为返回值是一个递归表达式。递归调用的次数过多时，会导致栈溢出。解决递归调用栈溢出的方法是通过尾递归优化。

尾递归优化是指，在函数返回的时候，调用自身本身，并且return语句不能包含表达式。

优化算法如下：

# -*- coding: utf-8 -*-
# @Time : 2022/3/28 11:03
# @File : function7.py
# @Software : PyCharm

def fact(n, pre, next):
    if (n == 2):
        return next
    return fact(n - 1, next, pre + next)


result = fact(100, 1, 1)
print(result)

运行结果：

354224848179261915075