面试题：C++递归函数复杂度分析之汉诺塔问题

Question

在C++中，实现一个解决汉诺塔问题的递归函数，汉诺塔由三根柱子A、B、C和n个大小不同的圆盘组成，初始状态下所有圆盘按照从小到大的顺序叠放在A柱上，目标是将所有圆盘移动到C柱上，每次只能移动一个圆盘，且在移动过程中，大圆盘不能放在小圆盘上面。请分析该递归函数的时间复杂度，并说明如何优化空间复杂度。

Answer 1

递归函数实现

#include <iostream>

// 汉诺塔递归函数
void hanoi(int n, char source, char auxiliary, char target) {
    if (n > 0) {
        // 将n - 1个圆盘从source移动到auxiliary
        hanoi(n - 1, source, target, auxiliary);
        // 将第n个圆盘从source移动到target
        std::cout << "Move disk " << n << " from " << source << " to " << target << std::endl;
        // 将n - 1个圆盘从auxiliary移动到target
        hanoi(n - 1, auxiliary, source, target);
    }
}

时间复杂度分析

汉诺塔问题的递归函数时间复杂度为$O(2^n)$。

1. 每次递归调用hanoi函数时，会产生两个子问题，即移动$n - 1$个圆盘的操作。
2. 随着$n$的增加，问题规模呈指数增长。对于$n$个圆盘，总的移动次数为$2^n - 1$。因此，时间复杂度为$O(2^n)$。

空间复杂度优化

1. 递归调用栈空间：原递归实现中，空间复杂度主要来自递归调用栈，最坏情况下为$O(n)$，因为递归深度最大为$n$。
2. 优化方法 - 迭代实现：可以使用栈（模拟递归调用栈）来实现迭代版本的汉诺塔算法，从而将空间复杂度优化到$O(1)$。具体思路是：
   • 用一个栈来模拟递归调用过程。
   • 每个栈元素记录当前任务的状态，包括当前要移动的圆盘数量、源柱、辅助柱和目标柱。
   • 通过循环和栈操作来模拟递归调用，避免直接的递归调用。

示例代码如下（迭代实现汉诺塔）：

#include <iostream>
#include <stack>

struct HanoiTask {
    int n;
    char source;
    char auxiliary;
    char target;
    HanoiTask(int n, char source, char auxiliary, char target) : n(n), source(source), auxiliary(auxiliary), target(target) {}
};

void hanoiIterative(int n, char source, char auxiliary, char target) {
    std::stack<HanoiTask> taskStack;
    taskStack.push(HanoiTask(n, source, auxiliary, target));

    while (!taskStack.empty()) {
        HanoiTask task = taskStack.top();
        taskStack.pop();

        if (task.n > 0) {
            taskStack.push(HanoiTask(task.n - 1, task.auxiliary, task.source, task.target));
            std::cout << "Move disk " << task.n << " from " << task.source << " to " << task.target << std::endl;
            taskStack.push(HanoiTask(task.n - 1, task.source, task.target, task.auxiliary));
        }
    }
}

这样，通过迭代实现，空间复杂度可以优化到$O(1)$。