汉诺塔问题的数学模型与规则

汉诺塔（Tower of Hanoi）是计算机科学与离散数学中的经典模型。该问题设定有三根柱子（通常标记为A、B、C）以及若干个尺寸互异的圆盘。初始状态下，所有圆盘按尺寸从小到大的顺序堆叠在起始柱上。目标是将所有圆盘移动至目标柱，且在移动过程中必须严格遵循以下物理约束：

• 每次操作仅允许移动一个圆盘。
• 任何时刻，大尺寸圆盘均不可放置在小尺寸圆盘之上。

该问题的最小移动步数具有明确的数学解析解，即 $2^n - 1$（其中 $n$ 为圆盘总数）。随着 $n$ 的增加，状态空间呈指数级膨胀，这使其成为评估算法时间复杂度与空间复杂度的理想基准。

递归与非递归：算法范式对比

递归范式的局限性

汉诺塔问题天然具备自相似性，因此递归是最直观的解法。然而，在实际工程环境中，深度递归会引发严重的系统级问题。每次函数调用都需要在调用栈（Call Stack）中分配栈帧以保存局部变量和返回地址。当圆盘数量 $n$ 较大时，递归深度达到 $n$ 层，极易触发栈溢出（Stack Overflow）异常，导致进程崩溃。

迭代范式的优势

非递归（迭代）算法通过显式的数据结构和循环控制流来替代隐式的系统调用栈。其核心优势在于：

• 内存可控性：将状态存储在堆内存（Heap）而非受限的栈内存中，彻底消除栈溢出风险。
• 执行效率：消除了频繁的函数上下文切换与栈帧分配开销，提升了底层执行效率。
• 状态可恢复性：显式保存的任务队列允许算法在任意时刻暂停、序列化或进行分布式调度。

基于显式栈的非递归算法设计

数据结构选型

为了将递归转化为迭代，我们需要引入"显式栈"（Explicit Stack）来模拟系统的调用栈。栈的后进先出（LIFO）特性完美契合了递归回溯的执行顺序。在汉诺塔问题中，栈内存储的元素不再是简单的数值，而是代表一次"移动任务"的元组，包含当前需要处理的圆盘数、起始柱、目标柱和辅助柱。

状态转换与任务调度

在递归逻辑中，移动 $n$ 个圆盘被分解为三个子任务： 1. 将 $n-1$ 个圆盘从起点移至辅助点。 2. 将第 $n$ 个圆盘从起点移至终点。 3. 将 $n-1$ 个圆盘从辅助点移至终点。

在迭代实现中，我们将这三个子任务作为独立的状态节点压入显式栈。由于栈的LIFO特性，为了保证任务按 1 -> 2 -> 3 的顺序执行，入栈顺序必须严格反转为 3 -> 2 -> 1。

Python代码实现与重构

递归基线实现

作为对比，以下是重构后的标准递归实现。该版本优化了基准条件（Base Case），当仅剩一个圆盘时直接输出，减少了不必要的递归展开。

def execute_hanoi_recursive(disk_count, start_pole, end_pole, mid_pole):
    """
    汉诺塔递归解法基线实现
    """
    if disk_count == 1:
        print(f"Move disk 1 from {start_pole} to {end_pole}")
        return
    
    # 1. 将 n-1 个盘子从起点移到辅助点
    execute_hanoi_recursive(disk_count - 1, start_pole, mid_pole, end_pole)
    
    # 2. 将最大的盘子从起点移到终点
    print(f"Move disk {disk_count} from {start_pole} to {end_pole}")
    
    # 3. 将 n-1 个盘子从辅助点移到终点
    execute_hanoi_recursive(disk_count - 1, mid_pole, end_pole, start_pole)

非递归迭代实现

以下代码展示了如何利用显式栈彻底消除递归调用。通过自定义任务元组，算法在单一的 `while` 循环中完成了所有状态流转。

def solve_hanoi_iterative(total_disks, source, target, auxiliary):
    """
    汉诺塔非递归解法：基于显式栈模拟递归调用
    """
    # 初始化任务栈，存储元组: (当前盘子数, 起点, 终点, 辅助点)
    task_stack = [(total_disks, source, target, auxiliary)]
    
    while task_stack:
        disks, src, dest, aux = task_stack.pop()
        
        # 基准条件：只剩一个盘子时直接移动
        if disks == 1:
            print(f"Move disk 1 from {src} to {dest}")
        else:
            # 注意：入栈顺序必须与期望的执行顺序相反
            
            # 任务3：将 n-1 个盘子从辅助点移动到终点
            task_stack.append((disks - 1, aux, dest, src))
            
            # 任务2：将当前最大的盘子从起点移动到终点
            task_stack.append((1, src, dest, aux))
            
            # 任务1：将 n-1 个盘子从起点移动到辅助点
            task_stack.append((disks - 1, src, aux, dest))

工程实践：单元测试与性能验证

单元测试设计

在工程交付中，算法的正确性必须通过自动化测试来保障。由于汉诺塔算法的核心输出是标准打印流，我们利用 `unittest.mock` 拦截 `print` 函数，对输出序列进行断言校验。

import unittest
from unittest.mock import patch

class TestHanoiIterative(unittest.TestCase):
    
    @patch('builtins.print')
    def test_iterative_hanoi_output(self, mock_print):
        # 执行2个盘子的非递归求解，起点A，终点C，辅助B
        solve_hanoi_iterative(2, 'A', 'C', 'B')
        
        # 定义期望的移动序列
        expected_calls = [
            "Move disk 1 from A to B",
            "Move disk 2 from A to C",
            "Move disk 1 from B to C"
        ]
        
        # 提取mock对象中记录的实际调用参数
        actual_calls = [call.args[0] for call in mock_print.call_args_list]
        
        # 断言实际输出与期望序列完全一致
        self.assertListEqual(actual_calls, expected_calls)

if __name__ == '__main__':
    unittest.main()

复杂度与优化探讨

从时间复杂度来看，无论是递归还是非递归实现，汉诺塔问题的最小移动步数恒为 $2^n - 1$，因此时间复杂度均为 $O(2^n)$。这是由问题本身的数学性质决定的，无法通过算法层面的优化来突破。

在空间复杂度方面，递归解法的空间复杂度为 $O(n)$，受限于系统调用栈的深度。非递归解法中，显式栈 `task_stack` 的最大深度同样为 $O(n)$（具体取决于树的深度），但其内存分配发生在堆区，不再受限于操作系统的线程栈大小限制。对于需要处理极深状态树的变种汉诺塔问题（如四柱汉诺塔），可以在状态元组中引入哈希缓存（Memoization）或位运算压缩，以进一步优化堆内存的占用率与状态检索效率。