python——递归函数
递归函数
1.  递归函数的定义：函数直接或间接的调⽤函数本⾝，则称该函数为递归函数。也就是说，如果在⼀个函数内部，调⽤⾃⾝本⾝，那么这个函数就称为递归函数。
2.  计算阶乘的算法就⽤到了递归函数，func（n）= n * func（n-1）
1#定义函数
2 >>> def func(n):
3if n==1:
4return 1
5return n*func(n-1)
6
7#调⽤函数
8 >>> func(1)
9 1
10 >>> func(5)
11 120
12 >>> func(100)
13 933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000
3.  递归函数的优点是逻辑简单清晰，缺点是过深的递归容易导致栈溢出
4.  尾递归：为了解决递归调⽤栈溢出的问题。尾递归是指，在函数返回的时候，调⽤⾃⾝，并且 return 语句中不能包含表达式。
尾递归和循环的效果⼀样，可以把循环看成⼀种特殊的尾递归函数。
⽤尾递归实现阶乘算法：
1 >>> def func(n):
2return func_iter(n,1)
3
4 >>> def func_iter(num,product):
5if num==1:
6return product
7return func_iter(num-1,num*product)
尾递归调⽤时，如果做了优化，栈不会增长，因此，⽆论多少次调⽤也不会导致栈溢出。
遗憾的是，⼤多数编程语⾔没有针对尾递归做优化，Python解释器也没有做优化，所以，即使把上⾯的 func（n）函数改成尾递归⽅式，也会导致栈溢出
5.汉诺塔问题：
1 >>> def move(n,a,b,c):  #n为圆盘数，a代表初始位圆柱，b代表过渡位圆柱，c代表⽬标位圆柱
2if n==1:
3print(a,'-->',c)
4else:
5#将初始位的n-1个圆盘移动到过渡位，此时初始位为a，上⼀级函数的过渡位b即为本级的⽬标位，上级的⽬标位c为本级的过渡位
6        move(n-1,a,c,b)
7print(a,'-->',c)
8#将过渡位的n-1个圆盘移动到⽬标位，此时初始位为b，上⼀级函数的⽬标位c即为本级的⽬标位，上级的初始位a为本级的过渡位编程递归函数
9        move(n-1,b,a,c)
10
11
12 >>> move(3,'A','B','C')
13 A --> C
14 A --> B
15 C --> B
16 A --> C
17 B --> A
18 B --> C
19 A --> C

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。