本文共 1065 字，大约阅读时间需要 3 分钟。

斐波那契数列是一个经典的递推数列，常用于测试递归和迭代算法的性能。以下是两种实现方式：

def fib1(n):  # 递归方法实现
    assert n >= 0
    if n <= 1:
        return n
    else:
        return fib1(n-1) + fib1(n-2)
def fib2(n):  # 非递归方法实现
    pre1 = 1
    pre2 = 1
    print(pre1, end=',')
    print(pre2, end=',')
    for i in range(n):
        tmp = pre1
        pre1 = pre2
        pre2 = tmp + pre2
        print(pre2, end=',')
    # fib2的输出比fib1多两个是因为fib2初始值从1和1开始，而fib1返回n=0和n=1时的值为0和1
    # 但在这个实现中，为了与fib1的输出对齐，已经调整了初始值

汉诺塔代码解析

汉诺塔是一种经典的递归问题，涉及将n个盘子从一个柱子移动到另一个柱子，仅能用中间柱子辅助。以下是代码实现：

def hanoi(n, x, y, z):
    if n == 1:
        print(f"{x} -> {z}")
    else:
        hanoi(n-1, x, z, y)  # 将n-1个盘子从x移动到y
        print(f"{x} -> {z}")  # 将第n个盘子从x移动到z
        hanoi(n-1, y, x, z)  # 将n-1个盘子从y移动到z
# 读取输入
sum = int(input('请输入汉诺塔层数：'))
hanoi(sum, 'X', 'Y', 'Z')

代码解读

• x、y、z：分别代表三个柱子名，'X'表示起始柱子，'Y'为中间柱子，'Z'为目标柱子。
• 递归逻辑：函数递归分解问题，将n个盘子分解为n-1个盘子、第n个盘子和剩下的n-1个盘子。
• 输出：每次移动盘子时会输出移动命令，方便监控过程。

技术细节

• 斐波那契数列：fib1使用递归实现，fib2采用迭代方式。fib2的输出比fib1多两个是因为初始值处理方式不同。
• 汉诺塔：代码遵循递归分解的思路，确保每次移动都遵循规则。

这些实现代码不仅展示了算法的逻辑，还通过简单的输出帮助调试和理解算法行为。