递归算法思想

特点

1. 递归过程一般通过函数或子过程来实现。
2. 递归算法在函数或子过程的内部，直接或间接地调用自己的算法。
3. 递归算法实际上是把问题转换成规模缩小的同类问题的子问题，然后递归调用函数或子过程来表示问题的解。

注意点

1. 递归是在过程或函数中调用自身的过程。
2. 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
3. 递归算法通常显得很简洁，但是运行效率较低，所以一般不提倡用递归算法设计程序。
4. 在递归调用过程中，系统用栈来存储每一层的返回点和局部量。如果递归次数过多，则容易造成栈溢出，所以一般不提倡用递归算法设计程序。

斐波那契数列

递归写法：

def fib_num(n):
    num_list = [0, 1]
    if n <= 1:
        return num_list[n]
    return fib_num(n - 1) + fib_num(n - 2)

n = 10
for i in range(n):
    print(fib_num(i), end=' ')  # 0 1 1 2 3 5 8 13 21 34 

Python 特有写法：

def fib(n):
    a, b = 0, 1
    while n:
        print(a, end=" ")
        a, b = b, a + b
        n -= 1

fib(10)  # 0 1 1 2 3 5 8 13 21 34 

汉诺塔问题

i = 1

def move(n, mfrom, mto):
    global i
    print("第%d步：将%d号盘子从%s -> %s" % (i, n, mfrom, mto))
    i += 1

def hanoi(n, A, B, C):
    if n == 1:
        move(1, A, C)
    else:
        hanoi(n - 1, A, C, B)
        move(n, A, C)
        hanoi(n - 1, B, A , C)

n = 2
hanoi(n, 'A', 'B', 'C')

# 输出
第1步：将1号盘子从A -> B
第2步：将2号盘子从A -> C
第3步：将1号盘子从B -> C

阶乘问题

def fact(n):
    if n <= 1:
        return 1
    else:
        return n * fact(n - 1)

n = 5
print(fact(n))  # 120