带记忆化的递归汉诺塔（Towers of Hanoi）算法的空间复杂度是多少？

1 普通无记忆化版本的空间复杂度纠正 #

你最初的猜测存在一个常见误区：普通无记忆化的递归汉诺塔空间复杂度不是O(2^(n-1))，实际是O(n)：

• 你提到的2^n -1是总递归调用次数，这个数值是对的，但空间复杂度统计的是程序运行过程中同时占用的最大内存，递归调用栈的内存只统计当前存活的栈帧：算法每次会先完整执行第一个n-1层的递归，等该递归完全返回释放栈帧后，才会执行磁盘移动，再执行第二个n-1层的递归。整个过程中调用栈的最大深度就是n，所以空间复杂度仅为O(n)。
• 顺带说明：普通版本的时间复杂度为O(2^n)，和总递归调用次数、总磁盘移动次数的量级一致。

2 你对记忆化的判断完全正确 #

汉诺塔递归不存在任何重复子问题，记忆化完全没有使用价值：

• 每个递归调用的唯一标识是参数组合(n, source, mid, target)，所有子问题的参数组合都是唯一的：比如将k个磁盘从A柱移到B柱，和将k个磁盘从A柱移到C柱，是完全不同的两个问题，没有任何可复用的重叠子问题结果，记忆化不会带来任何时间优化。

3 加记忆化后的空间复杂度确实会飙升 #

如果强行给递归加上记忆化缓存所有调用结果：

• 总共有2^n -1个唯一的调用记录需要存储，这时候空间复杂度会从原来的O(n)直接升到O(2^n)，属于完全没必要的负优化，所以该递归算法完全不需要使用记忆化。

def hanoi_tower_solution(n, source, mid, target):
    if n == 1:
        disk_move(source, target)
    else:
        hanoi_tower_solution(n-1, source, target, mid)
        disk_move(source, target)
        hanoi_tower_solution(n-1, mid, source, target)

内容的提问来源于stack exchange，提问作者Thang Tran