这个复杂的递归代码是如何工作的？

Question

我正在尝试理解这种递归。我知道阶乘函数中的递归是如何工作的，但是当它到了像这样的复杂递归时，我就迷惑了。对我来说最令人困惑的部分是下面的代码

str.split('').map( (char, i) => 
    permutations( str.substr(0, i) + str.substr(i + 1) )map( p => char + p))

首先，对于"abc"，它将拆分成["a","b","c"]并遍历map函数，然后遍历第二个map函数，分别用a、b和c包装每个返回。然而，我对递归部分感到非常困惑。

我认为"a"中第一个值为str作为"abc"的递归将返回"bc"，第二个值为"bc"的递归将返回"c"，依此类推。

但是，当我运行这段代码查看清晰的递归时，它返回

[ [ [ 'c' ], [ 'b' ] ], [ [ 'c' ], [ 'a' ] ], [ [ 'b' ], [ 'a' ] ] ]

这对我来说是最困惑的。我就是不明白这个递归是如何返回这些值的。有没有人可以更详细地介绍一下这是如何工作的，比如一步一步地说明你的思维过程？

我是一个视觉学习者。谢谢你的帮助。

function permutations(str) {
 return (str.length <= 1) ? [str] :
      // Array.from(new Set(
        str.split('')
              .map( (char, i) => 
                     permutations( str.substr(0, i) + str.substr(i + 1))
                           .map( p => char + p))
            //  .reduce( (r, x) => r.concat(x), [])
        //  ));
}

permutations('abc')

Answer 1

让我们检查一下permutations('abc')。

将'abc'转换为['a','b','c']以进行映射

地图

一个

首先是char='a',i=0。请注意，permutations(str.substr(0, i) + str.substr(i + 1))的意思是“获得除我正在查看的字符之外的所有字符的排列。在本例中，这意味着permutations('bc')。让我们假设这给出了正确的输出['bc','cb']，作为归纳假设。

然后，.map(p => char + p)告诉我们在每个较小的排列前面加上我们正在查看的字符('a')。这就产生了['abc',acb']。

B

遵循相同的逻辑，char='b',i=1'。permutations('ac') == ['ac','ca']。最终输出为['bac','bca']

C

遵循相同的逻辑，char='c',i=2'。permutations('ab') == ['ab','ba']。最终输出为['cab','cba']。

因此，函数的总体输出将是[['abc','acb'],['bac','bca'],['cab','cba']]...

Answer 2

这实际上是对permutations的一个非常不寻常的定义，我碰巧从来没有见过。:)

在伪代码中，人们通常看到的简单递归定义是

perms [x, ...xs] = [ [...as, x, ...bs] | p <- perms xs, (as, bs) <- splits p]

但这一次

perms2 xs = [ [x, ...p] | (as, [x, ...bs]) <- splits xs, p <- perms2 [...as, ...bs]]

(使用列表理解和模式；消除空的列表情况；使用splits的“自然”定义，它构建了将列表分成两部分的所有可能性的列表)。

这里有一种二元性..。有意思的。而不是“简单的”-recursive。:)

或者，随着一些更多的命名函数以明显的方式实现，

perms [x, ...rest] = [ i | p <- perms rest, i <- inserts x p]
                   = flatMap (inserts x) (perms rest)

--- and this version, 
perms2 xs = [ [x, ...p] | (x, rest) <- picks xs, p <- perms2 rest]

另请参阅：

• Understanding Peter Norvig's permutation solution in PAIP