13.递归函数

目录：
1.递归的介绍
2.fibonacci数列
3.递归和循环的比较

1.递归的介绍

函数直接或间接调用自身就是递归
递归需要有边界条件、递归前进段、递归返回段
递归一定要有边界条件

2.fibonacci数列

2.1循环实现

[root@node05 python]# vim test.py 
a=0
b=1
print(a,b,end=' ')
for i in range(5):
    a,b = b,a+b
    print(b,end=' ')
[root@node05 python]# python3 test.py 
0 1 1 2 3 5 8 

2.2递归实现

[root@node05 python]# vim test.py 
def fib(n):
    return 1 if n < 2 else fib(n-1) + fib(n-2)
for i in range(7):
    print(fib(i),end=' ')
[root@node05 python]# python3 test.py 
1 1 2 3 5 8 13

递归要求：
递归一定要有退出条件，递归调用一定要执行到这个退出条件
没有退出条件的递归调用，就是无限调用
递归调用的深度不宜过深
Python对递归调用的深度做了限制，以保护解释器
超过递归深度限制，抛出RecursionError:maxinum recursion depth exceeded超出最大深度
sys.getrecursionlimit()

3.递归和循环的比较

3.1for循环

[root@node05 python]# vim test.py 
import datetime
start = datetime.datetime.now()
pre = 0
cur = 1
print(pre,cur, end=' ')
n = 35
for i in range(n-1):
    pre, cur = cur, pre + cur
print(cur, end=' ')
delta = (datetime.datetime.now()-start).total_seconds()
print(delta)
[root@node05 python]# python3 test.py 
0 1 9227465 2.5e-05

3.2递归实现

[root@node05 python]# vim test.py 
import datetime
pre = 0
cur = 1
print(pre,cur, end=' ')
n = 35
start = datetime.datetime.now()
def fib(n):
    return 1 if n < 2 else fib(n-1) + fib(n-2)
for i in range(n):
    num = fib(i)
print(num, end=' ')
delta = (datetime.datetime.now() - start).total_seconds()
print(delta)
[root@node05 python]# python3 test.py 
0 1 9227465 5.254317

递归的性能分析：
循环稍微复杂一些，但是只要不是死循环，可以多次迭代出最终结果
递归函数代码极其简单易懂，但是只能获取到最外层的函数调用，内部递归结果都是中间结果。而且给定了一个n都要进行近2n次递归，深度越深，效率越低。为了获取斐波那契数列需要外面在套一个N次的循环，效率就更低了。
递归还有深度限制，如果递归复杂，函数反复压栈，栈内存很快就溢出了

3.3递归的优化

import datetime
start = datetime.datetime.now()
pre = 0
cur = 1 # No1
print(pre, cur, end=' ')
def fib(n, pre=0,cur=1): # recursion
    pre, cur = cur, pre + cur
    print(cur, end=' ')
    if n == 2:
        return
    fib(n-1, pre, cur)
fib(35)
delta = (datetime.datetime.now()-start).total_seconds()
print(delta)
[root@node05 python]# python3 test1.py 
0 1... 9227465 5.4e-05

总结：

改进后的fib函数和循环思想类似，参数n是边界条件，用n来计数
前一次的计算结果直接作为函数的实参，效率较高
和循环比较，性能相近。