面试题 08.06. 汉诺塔问题

[swiftwind0405]

方法一：递归

解题思想：
看知乎的这个帖子：如何理解汉诺塔的递归？。
主要是总结出递归的这个函数，其实自己一步步走一遍的话，还是能明白的。
重点思想是理解开始柱，中转柱，目标柱这三个概念，具体还是看上面的帖子吧，不再赘述。

代码：

var hanota = function(A, B, C) {
    const move = (n, from, buffer, to) => {
        if (n === 1) {
            console.log(A, '--->', C);
            to.push(from.pop());
        } else {
            move(n - 1, from, to, buffer);
            console.log(A, '--->', C);
            move(1, from, buffer, to);
            move(n - 1, buffer, from, to);
        }
    }
    move(A.length, A, B, C);
};

复杂度分析：

• 时间复杂度：O(2^n-1)：一共需要移动的次数。（不会分析！TODO！）
• 空间复杂度：O(1)：没有用使用其它的空间。