最近在学习算法的时候，接触了一个叫递归(Recursion)的东西。
现在开始面向自己整理。
希望我看完之后能搞清楚几个问题。
1. 基本问题Q&A
1-1 递归是什么？
递归就是自身调用自己。
这篇文章写的还不错。
推荐网页 Python 递归函数
这里推荐一个李永乐老师的视频，关于汉诺塔的。下面有。▼▼▼
Youtube需要科学上网才能打开。B站也有，这里自己麻烦手动汉诺塔游戏应该可以找到。
1-2 迭代和递归有什么区别？
共同点: 都是多次重复一个函数
不同点: 递归是自己调用自己，逐渐缩小范围。这个缩小范围就决定了下面的问题的答案，就是必须要有一个出口，每一次递归必须要缩小范围，否则就没意义。
迭代是自己执行了很多次，每次执行都更接近目标值。
比如下面就是关于阶乘n！实现的一组对比。
# 迭代实现
def iterative_of_factorial(n):
result = 1
for i in range(2,n+1):
result *= i
return result
print(iterative_of_factorial(5))
# 递归实现
def recursive_of_factorial(n):
if n == 1:
return 1
else:
return n * recursive_of_factorial(n-1)
print(recursive_of_factorial(5))
# 多看几遍可以看出来，递归最后return的是自身。而迭代通过的是不断重复运行下一个函数。
1-3 递归Code的时候要注意什么
a. 自己调用自己
b. 必须有结束条件作为递归出口，不然死循环了。
2. 实现一个简单递归并解析
从简单的一步步抽丝剥茧开始解析。
因为上面有了简单的阶乘递归，那么我们实现一个加法好了。
def sum_of_recrusive(number):
if number == 0:
return 0
else:
return number + sum_of_recrusive(number-1)
print(sum_of_recrusive(5))
# result
# 15
我们来解析一下上面的方法。
因为打代码看起来不是很具有整体性。我直接把代码截图截下来的，建议整体一起看。
3. 实现稍微复杂的递归
这里主要实现2个函数。斐波那契数列和汉诺塔。
如何用code写出来呢。我总结了一下规律大概就是这几步吧。
找规律
找条件
查漏补缺(主要是考虑各种极值问题，比如0，1这种特殊情况)
3-1 斐波那契数列
这个数列是很有名的可以用递归来实现的数列。
不懂含义的建议先谷歌一下。
这里分为递归和迭代2种方法来对比实现。2种方法一个给的需要几个数列，一个是给了数列范围。别看错。
参考网页: Python Program for Fibonacci numbers
# 递归写法，给列表个数返回列表
def fibonacci_of_rec(number: int) -> list:
"""1.递归实现"""
if number == 1:
return 0
elif number == 2:
return 1
else:
return fibonacci_of_rec(number-1) + fibonacci_of_rec(number-2)
def print_fib(number: int) -> list:
"""2.打印"""
fib_list = []
for i in range(1,number+1):
fib_list.append(fibonacci_of_rec(i))
return fib_list
print(print_fib(10))
# resule
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
# 迭代写法，给数字范围返回列表
def fibonacci_of_iter(n: str) -> list:
fib_list = []
a, b = 0, 1
while a < n:
fib_list.append(a)
a, b = b, a + b
return fib_list
print(fibonacci_of_iter(1000))
# result
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987]
如果你感觉无从下手，那么就要先找规律，规律先找到，再去考虑递归条件的问题。
刚开始不要想着直接写代码，而是现在脑海里思考一下具体的实现步骤。
3-2 汉诺塔
首先要知道汉诺塔是什么，这个就是一个很典型的递归思想。
主要就是通过缩小范围，来进行递归。看代码之前要了解什么是汉诺塔。
参考网页:Python Program for Tower of Hanoi
参考网页:python中的汉诺塔递归算法的具体运算过程是怎样的？
def move(n: int, a: str, b, c):
if n == 1:
print('move', a, '-->', c)
else:
move(n-1,a,c,b)
move(1,a,b,c)
move(n-1,b,a,c)
move(2,'A','B','C')
------result-------
move A --> B
move A --> C
move B --> C
move(3,'A','B','C')
------result-------
move A --> C
move A --> B
move C --> B
move A --> C
move B --> A
move B --> C
move A --> C
4.最后的最后
动手写Code！动手写Code！动手写Code！
书读百遍，其义自见。ー晋·陈寿·三国志
代码也是一样的，我真的写之前看了好多文章都没搞懂，最后真的是自己写一遍又一遍才明白了一点点。所以还是动起手吧。