『Python整理向』「了解一下到底什么是递归(Recursion)」| Code | Chihokyo BLOG

最近在学习算法的时候，接触了一个叫递归(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！

书读百遍，其义自见。ー晋·陈寿·三国志
代码也是一样的，我真的写之前看了好多文章都没搞懂，最后真的是自己写一遍又一遍才明白了一点点。所以还是动起手吧。