Self-study Python Fish-C Note14 P50to51

函数 (part 4)

本节主要讲函数 递归
递归 (recursion)

递归就是函数调用自身的过程
示例1：

1. def fun1(i):
2.     if i > 0:
3.         print('something')
4.         i-=1
5.         fun1(i)
6. fun1(5) # 这样就会打印五遍 'something'

复制代码

1. something
2. something
3. something
4. something
5. something

复制代码

要让递归正常工作，肯定要有一个结束条件，并且每次调用都会向着这个结束条件去推进。比如上面的例子，加上一个 if 条件语句，让递归在恰当的时候举行回。归小心无限调用的死循环（可以使用 Ctrl + C 强制结束）
有这样一句话“天才程序员用递归，普通程序员用迭代”。接下来我们用几个例子来批判比力一下相同任务递归与迭代的区别：
示例2，求一个数的阶乘：
在数学中，正整数的阶乘（英语：factorial）是全部小于等于该数的正整数的积，记为 n! 比方5的阶乘表示为 5!,其值为120

1. # 使用迭代
2. def fact1(n):
3.     result = n
4.     for i in range(1,n):
5.         result*=i
6.     return result
7. print(fact1(5))
8. print(fact1(10))
9. print(fact1(1))

复制代码

1. 120
2. 3628800
3. 1

复制代码

1. # 使用递归
2. def fact2(n):
3.     if n == 1:
4.         return 1
5.     else:
6.         return n*fact2(n-1)
7. print(fact2(5))
8. print(fact2(10))
9. print(fact2(1))  
10. # print(fact2(-1))  这个如果运行会进入无限循环，挂掉

复制代码

1. 120
2. 3628800
3. 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项开始 ，每一项都等于前两项之和。

1. # 迭代法
2. def fib1(n):
3.     a = 1
4.     b = 1
5.     c = 1
6.     while n > 2:
7.         c = a + b
8.         a = b
9.         b = c
10.         n-=1
11.     return c
12. print(fib1(1))
13. print(fib1(2))
14. print(fib1(3))
15. print(fib1(4))
16. print(fib1(5))
17. print(fib1(6))

复制代码

1. 1
2. 1
3. 2
4. 3
5. 5
6. 8

复制代码

1. # 递归法
2. def fib2(n):
3.     if n==1 or n==2:
4.         return 1
5.     else:
6.         return fib2(n-1)+fib2(n-2)
7. print(fib2(1))
8. print(fib2(2))
9. print(fib2(3))
10. print(fib2(4))
11. print(fib2(5))
12. print(fib2(6))

复制代码

1. 1
2. 1
3. 2
4. 3
5. 5
6. 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 杆，但都必须遵照上述两条规则

1. def hanoi(n,x,y,z):
2.     if n==1:
3.         print(x,'-->',z) # 如果只有1层，直接将金片从 x 移动到 z
4.     else:
5.         hanoi(n-1,x,z,y) # 将 x 上的 n-1 个金片移动到 y
6.         print(x,'-->',z) # 将放在最下面的金片从 x 移动到 z
7.         hanoi(n-1,y,x,z) # 将 y 上的 n-1 个金片移动到 z
9. hanoi(5,'A','B','C')

复制代码

1. A --> C
2. A --> B
3. C --> B
4. A --> C
5. B --> A
6. B --> C
7. A --> C
8. A --> B
9. C --> B
10. C --> A
11. B --> A
12. C --> B
13. A --> C
14. A --> B
15. C --> B
16. A --> C
17. B --> A
18. B --> C
19. A --> C
20. B --> A
21. C --> B
22. C --> A
23. B --> A
24. B --> C
25. A --> C
26. A --> B
27. C --> B
28. A --> C
29. B --> A
30. B --> C
31. 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企服之家，中国第一个企服评测及商务社交产业平台。