需要帮助理解递归函数以生成字符串的所有组合

Question

我遇到了 this code，但是我很难弄清楚这个函数的流程是如何工作的。

function combinations(str) {
    var fn = function(active, rest, a) {
        if (!active && !rest)
            return;
        if (!rest) {
            a.push(active);
        } else {
            fn(active + rest[0], rest.slice(1), a);
            fn(active, rest.slice(1), a);
        }
        return a;
    }
    return fn("", str, []);
}

我有 console.logged 一堆语句，但我在递归中迷路了。具体来说，我不明白返回两个 fn 中的第一个后发生了什么。它只是返回 a，但对我来说，似乎第二个 fn 知道接受返回的 a。这是如何运作的？它不应该像这样需要一个变量赋值吗：

a = fn(active + rest[0], rest.slice(1), a);
fn(active, rest.slice(1), a);

Answer 1

好吧，如果你想了解特定的算法，关键的洞察力是 a 变量累积结果 by reference -- 较低级别的调用combinations() 将单个元素推到 a 上，函数最终 returns 累积结果。

一个好的打印语句可以帮助理解这样的情况。这是添加了打印输出的代码，显示您所处的递归级别。我将 a 重命名为 accum 以使其更加明显：

function combinations(str) {
  var fn = function(active, rest, accum, level) {
    console.log(new Array(level).join('--'),
                ' active: \'' + active + '\'',
                'rest: \'' + rest + '\'',
                'accum:', accum);
    if (!active && !rest)
      return;
    if (!rest) {
      accum.push(active);
    } else {
      fn(active + rest[0], rest.slice(1), accum, level + 1);
      fn(active, rest.slice(1), accum, level + 1);
    }
    return accum;
  }
  return fn("", str, [], 1);
}

结果：

combinations('abc')
  active: '' rest: 'abc' accum: []
--  active: 'a' rest: 'bc' accum: []
----  active: 'ab' rest: 'c' accum: []
------  active: 'abc' rest: '' accum: []
------  active: 'ab' rest: '' accum: [ 'abc' ]
----  active: 'a' rest: 'c' accum: [ 'abc', 'ab' ]
------  active: 'ac' rest: '' accum: [ 'abc', 'ab' ]
------  active: 'a' rest: '' accum: [ 'abc', 'ab', 'ac' ]
--  active: '' rest: 'bc' accum: [ 'abc', 'ab', 'ac', 'a' ]
----  active: 'b' rest: 'c' accum: [ 'abc', 'ab', 'ac', 'a' ]
------  active: 'bc' rest: '' accum: [ 'abc', 'ab', 'ac', 'a' ]
------  active: 'b' rest: '' accum: [ 'abc', 'ab', 'ac', 'a', 'bc' ]
----  active: '' rest: 'c' accum: [ 'abc', 'ab', 'ac', 'a', 'bc', 'b' ]
------  active: 'c' rest: '' accum: [ 'abc', 'ab', 'ac', 'a', 'bc', 'b' ]
------  active: '' rest: '' accum: [ 'abc', 'ab', 'ac', 'a', 'bc', 'b', 'c' ]
[ 'abc', 'ab', 'ac', 'a', 'bc', 'b', 'c' ]

需要帮助理解递归函数以生成字符串的所有组合

Need help understanding recursive function to generate all combinations of a string

javascript

recursion

combinations