数据结构 - 递归（汉诺塔）

一、调用 collections 中的 deque（双端链表）实现递归的栈操作

# 用栈模拟递归调用

# 调用双端列表
from collections import deque

class Stack:

    def __init__(self):
        self._deque = deque()

    # 调用 deque 中的 append 方法
    def push(self,value):
        return self._deque.append(value)

    # 调用 duque 中的 pop 方法
    def pop(self):
        return self._deque.pop()

    # 出栈条件，不不为空则 pop
    def is_empty(self):
        return len(self._deque) == 0


def print_num_use_stack(n):
    s = Stack()

    # 入栈
    while n > 0:
        s.push(n)
        n -= 1

    # 出栈
    while not s.is_empty():
        print(s.pop())

def test():
    print_num_use_stack(10)

test()

二、尾递归
尾递归将递归调用放在了函数的最后。因为普通递归的每一机递归都产生了新的局部变量，必须创建新的调用栈，随着递归深度的增加，创建的栈越来越多，造成爆栈。优化可使尾递归的每一级调用公用一个栈。

def print_num_recursive(n):
    if n > 0:
        pring(n)
        print_num_recursive(n-1)

三、汉诺塔问题

def HanoiMove(n, source, dest, intermediate):
    if n >= 1:  # 递归出口，只剩一个盘子
        HanoiMove(n - 1, source, intermediate, dest)
        print("Move %s -> %s" % (source, dest))
        HanoiMove(n - 1, intermediate, dest, source)


HanoiMove(3, 'A', 'C', 'B')

解析：汉诺塔问题是一个典型的递归问题。设有 A、B、C杆分别是原始杆、中转杆和目标杆，要将A杆的盘都挪到C杆上。将问题划分为如下两个操作：

（1）只留下最大的盘，其余盘挪到B杆，将其看作一个整体，具体怎么挪先不管；可以得到挪动单个盘的操作：A➡️C
（2）将B杆上的这些盘看作一个整体挪动到C杆上，完成挪动。

递归操作（1），完成的是：由 A-目标杆 将 n-1 个盘挪到 B-中转杆
递归操作（2），完成的事：由 B-中转杆 将 n-1 个盘挪到 C-目标杆

通过逆向的递归方法即可完成将所有盘由 A 挪到 C 的操作。