Self-study Python Fish-C Note14 P50to51
函数 (part 4)本节主要讲函数 递归
递归 (recursion)
递归就是函数调用自身的过程
示例1：
def fun1(i):
if i > 0:
print('something')
i-=1
fun1(i)
fun1(5) # 这样就会打印五遍 'something'
something
something
something
something
something
要让递归正常工作，肯定要有一个结束条件，并且每次调用都会向着这个结束条件去推进。比如上面的例子，加上一个 if 条件语句，让递归在恰当的时候举行回。归小心无限调用的死循环（可以使用 Ctrl + C 强制结束）
有这样一句话“天才程序员用递归，普通程序员用迭代”。接下来我们用几个例子来批判比力一下相同任务递归与迭代的区别：
示例2，求一个数的阶乘：
在数学中，正整数的阶乘（英语：factorial）是全部小于等于该数的正整数的积，记为 n! 比方5的阶乘表示为 5!,其值为120
# 使用迭代
def fact1(n):
result = n
for i in range(1,n):
result*=i
return result
print(fact1(5))
print(fact1(10))
print(fact1(1))
120
3628800
1
# 使用递归
def fact2(n):
if n == 1:
return 1
else:
return n*fact2(n-1)
print(fact2(5))
print(fact2(10))
print(fact2(1))
# print(fact2(-1))这个如果运行会进入无限循环，挂掉
120
3628800
1
以 fact2(5) 为例，代码中实际做的如下：
递归过程结果fact2(5) = 5 * fact2(4)——> fact2(5) = 5 * 4 * 3 * 2 * 1fact2(4) = 4 * fact2(3)——> fact2(4) = 4 * 3 * 2 * 1fact2(3) = 3 * fact2(2)——> fact2(3) = 3 * 2 * 1fact2(2) = 2 * fact2(1)——> fact2(2) = 2 * 1fact2(1) = 1——> fact2(1) = 1 示例3，斐波那契数列:
斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称“兔子数列”，其数值为 1，1，2，3，5，8，13，21，34，55，89……这个数列从第3项开始 ，每一项都等于前两项之和。
# 迭代法
def fib1(n):
a = 1
b = 1
c = 1
while n > 2:
c = a + b
a = b
b = c
n-=1
return c
print(fib1(1))
print(fib1(2))
print(fib1(3))
print(fib1(4))
print(fib1(5))
print(fib1(6))
1
1
2
3
5
8
# 递归法
def fib2(n):
if n==1 or n==2:
return 1
else:
return fib2(n-1)+fib2(n-2)
print(fib2(1))
print(fib2(2))
print(fib2(3))
print(fib2(4))
print(fib2(5))
print(fib2(6))
1
1
2
3
5
8
此时：
调用代码过程结果fib2(1)直接去到 return 11fib2(2)直接去到 return 21fib2(3)fib2(3)=fib2(2)+fib2(1)=22fib2(4)fib2(4)=fib2(3)+fib2(2)=fib2(2)+fib2(1)+fib2(2)3fib2(5)fib2(5)=fib2(4)+fib2(3)=fib2(3)+fib2(2)+fib2(2)+fib2(1)=fib2(2)+fib2(1)+2*fib2(2)+fib2(1)=55fib2(6)…8……… 如果我们使用递归计算第 120 个数 即 fib2(120)， 我们会发现计算了很长时间依然无法计算出结果。反而，使用迭代 fib1(120) 结果计算的很快。这就表现了递归和迭代之间的效率问题。每一次调用递归函数，他并不会立刻返回，而是要比及最底层的谁人函数返回，然后在一层一层往上走，这个过程黑白常泯灭资源的。
汉诺塔
有三根杆子A，B，C。A杆上有 N 个 (N>1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将全部圆盘移至 C 杆：
(1) 每次只能移动一个圆盘；
(2) 大盘不能叠在小盘上面。
提示：可将圆盘临时置于 B 杆，也可将从 A 杆移出的圆盘重新移回 A 杆，但都必须遵照上述两条规则
https://i-blog.csdnimg.cn/direct/4b63bd35118c4d9ea06dd4cdd30542cf.png
def hanoi(n,x,y,z):
if n==1:
print(x,'-->',z) # 如果只有1层，直接将金片从 x 移动到 z
else:
hanoi(n-1,x,z,y) # 将 x 上的 n-1 个金片移动到 y
print(x,'-->',z) # 将放在最下面的金片从 x 移动到 z
hanoi(n-1,y,x,z) # 将 y 上的 n-1 个金片移动到 z
hanoi(5,'A','B','C')
A --> C
A --> B
C --> B
A --> C
B --> A
B --> C
A --> C
A --> B
C --> B
C --> A
B --> A
C --> B
A --> C
A --> B
C --> B
A --> C
B --> A
B --> C
A --> C
B --> A
C --> B
C --> A
B --> A
B --> C
A --> C
A --> B
C --> B
A --> C
B --> A
B --> C
A --> C
总结递归函数的实验逻辑：递归函数在调用的时候不会直接立刻的去返回，而是经过层层调用，直到遇到符合条件的时候再触发返回机制，接着再逐层的返回。留意，递归函数肯定要有一个结束条件
附言：
题目：Self-study Python Fish-C Note-14 P50-P51
本文为自学B站上鱼C的python课程随手做的笔记。一些概念和例子我个人为更好的明白做了些查询和补充
因本人程度有限，如有任何问题，接待大家批评指正！
原视频链接：https://www.bilibili.com/video/BV1c4411e77t?p=8
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]