思维系列（01）——递归思维（斐波那契数列）

问题描述

(1) 有这样一个游戏：有两个人，第一个人先从1和2中挑选一个数字，第二个人可以在对方的基础上加1或者加2，然后又轮到第一个人，他也可以选择加1或者加2，之后再把选择权交给对方，这样对方交替的选择加1或者加2，谁先加到20，谁就赢了。对于这个游戏，你用什么策略保证一定能赢。

案例分析

如果要抢到20， 就需要抢到17，因为无论对方加1或者加2，你都可以加到20。而想要抢到17，就要抢到14，以此类推，就必须抢到11，8， 5， 2。
因此，只要第一个人抢到2，他就赢定了。

问题描述

(2) 按照上述方法，再不考虑谁输谁赢的情况下，从开始(以1或者2为起点)加到20， 有多少种不同的递加过程？比如说1，4，7，10，12， 15， 18， 20算一种；2， 5， 8， 11， 14， 17， 20又是一种。那么一共会有多少种这样的过程呢？

案例分析

假定数到20有F(20)种路径，那么到达20这个数字前一步只有两种可能情况，即从18直接跳到20，或者从19跳到20.
由于从18跳到20和从19跳到20是不同的，因此到达20的路径数量，其实就是到达18和路径数量，加上到达19的路径数量，也就是说，F(20)=F(18)+F(19)。类似的F(19)=F(18)+F(17)，这就是递推公式。
最后，F(1)只有一种可能，就是1， F(2)有两种可能，F(2)=2,就可以知道F(3),从而可以知道F(4), 类似的可以知道F(20)
聪明的你，一定看出来了，这就是斐波那契数列

# 递推实现斐波那契数列
def iterative_fibonacci(n):
    a, b = 1, 2
    # n-2的原因是除去前两个数
    for i in range(n-2):
        a, b = b, a+b
    return b
    
    
num = 30
ret_20 = iterative_fibonacci(num)
print(ret_20)

# 逆向递归实现斐波纳妾数列
def recursive_fibonacci(n):
    if n == 2:
        return 2
    if n == 1:
        return 1
    return recursive_fibonacci(n-1) + recursive_fibonacci(n-2)


ret_20 = recursive_fibonacci(num)
print(ret_20)

递归思维
递归思维是一种以结果为导向，反向追寻，直到追寻到原点(递归的终止条件)的思维方式，一旦原点问题得到解决，其后面的问题都会迎刃而解。正如埃隆-马斯克（Elon Musk）等人常说的“第一性原理”

参考书籍：
[1]张玉宏. Python极简讲义(一本书入门数据分析与机器学习).5,164,2020.