2

所以，我正在学习递归，我正在处理一个需要数组中元素的所有变体的编码挑战。

我被指给了Heap 的算法，这就是我到目前为止在 JavaScript 中制定的内容。

function generate(n, array) {
    if (n == 1) {
        return array;
    }
    else {
        for (var i = 0; i < n - 1; i++) {
            generate(n - 1, array);
            if (n % 2 == 0) {
                swap(array[i], array[n - 1]);
            }
            else {
                swap(array[0], array[n - 1]);
            }
        }
        generate(n - 1, array);
    }
}

请忽略我没有将“交换”实例翻译成 JavaScript 的事实。

我有点不确定如何准确地遍历这个算法的递归部分。

假设我有数组：[A,B,C,D,E]。我相信我将传递给外部函数的参数是：

generate(5, [A,B,C,D,E]);

在这种情况下，n 不等于 1，所以我将继续讨论“else”部分。我遇到了 for 循环，因为 n 是 5，所以它执行。

Next: 函数调用自身，但这次的参数是：

generate(4, [A,B,C,D,E]);

这就是我的困惑开始的地方：

当我经历这个时，我是继续“if”/“else”条件还是（在递归调用之后）回到外部函数的最开始？

更新

下面是 Heap 算法的完全翻译的 JavaScript 版本。

function generate(n, array) {
//console.log("ENTER", n, array)

if (n == 1) {

    console.log(array);
}

else {

    for (var i = 0; i < n - 1; i++) {
        //console.log("RECUR", n-1, array)


        generate(n - 1, array);

        if (n % 2 == 0) {
            //console.log("SWAP ", n, array)

            var one = array[i];
            var two = array[n - 1];

            array[i] = two;

            array[n - 1] = one;

            //swap(array[i], array[n - 1]);
        }

        else {
            //console.log("SWAP ", 0, n-1)

            var first = array[0];
            var second = array[n - 1];

            array[0] = second;

            array[n - 1] = first;


            //swap(array[0], array[n - 1]);
        }
         //console.log("array", array)
    }

    //console.log("RECUR 2", n-1, array)

    generate(n - 1, array);
}

//console.log("LEAVE", n, array)

}

我在纸上遍历它，直到我再次重复[A，B，C，D]。

以为我搞砸了，我决定实施 Prune 的控制台输出建议，看看控制台中发生了什么，这很有帮助。

修复一个小错误后，它现在工作得很好。

感谢所有帮助过的人！

4

2 回答 2

3

在这一点上，我的典型答案是，如果您在纸上遍历算法时遇到困难，请不要！让电脑替你做。插入一堆console.log命令来跟踪执行。跟踪每个例程和调用的进入和退出，包括有用的值。

function generate(n, array) {
    console.log("ENTER", n, array)
    if (n == 1) {
        return array;
    }
    else {
        for (var i = 0; i < n - 1; i++) {
            console.log("RECUR", n-1, array)
            generate(n - 1, array);
            if (n % 2 !== 0) {
                console.log("SWAP ", n, array)
                swap(array[i], array[n - 1]);
            }
            else {
                console.log("SWAP ", 0, n-1)
                swap(array[0], array[n - 1]);
            }
            console.log("array", array)
        }
        console.log("RECUR 2", n-1, array)
        generate(n - 1, array);
    }
    console.log("LEAVE", n, array)
}

这会给你一个可爱的执行跟踪。为了提高可读性，将输出的每一行缩进 2*(5-n) 个空格。

于 2016-11-14T22:57:29.793 回答
1

让我列举一下你的台词，这样我们就可以更容易地引用它们（见下文）

您从generate(5, [A,B,C,D,E]);最多generate(4, [A,B,C,D,E]);（第 7 行）走到（第 7 行），然后您generate第二次进入，但尚未完成第一次通话，因此您将暂停到第一次通话并开始与第二次通话

现在（第二次通话）n=4，所以你再次到达第 7 行，但这次generate(3, [A,B,C,D,E])开始第三次通话（没有完成之前的通话）

第 4 次通话generate(2, ...)和第 5 次通话也是如此generate(1, ...)，这是事情开始发生变化的时候

在第 5 次调用n=1中，因此第 2 行的条件 eval 为 true 并array返回，然后我们回到了我们来自的地方，即第 7 行的第 4 次调用，返回的数组什么也不做（它没有被分配或任何东西）然后我们在第 4 次调用时到达第 8 行（第一次），n=2因此第二次swap发生并i递增，然后回到第 7 行，我们再次调用generate(1, ...)相同的结果......等等

01. function generate(n, array) {
02.     if (n == 1) {
03.         return array;
04.     }
05.     else {
06.         for (var i = 0; i < n - 1; i++) {
07.             generate(n - 1, array);
08.             if (n % 2 !== 0) {
09.                 swap(array[i], array[n - 1]);
10.             }
11.            else {
12.                swap(array[0], array[n - 1]);
13.            }
14.        }
15.        generate(n - 1, array);
16.    }
17. }
于 2016-11-14T23:04:12.847 回答