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

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"，而 str 值为 "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

我更喜欢分析和创建递归解决方案的一种方法是像数学归纳一样工作¹。

诀窍是表明该函数为我们的基本情况返回正确的值，然后表明如果它为我们更简单的情况返回正确的值，它也将为我们当前的情况返回正确的值。然后我们知道它适用于所有值，只要每个递归调用都是针对一些最终导致基本情况的更简单的情况。

所以看看你的函数。我重新格式化了它以使讨论更容易，并且我恢复了 reduce调用你已经注释掉了。事实证明，这是正确执行此操作所必需的(尽管我们将在下面讨论更现代的替代方案。)您还注释掉了 Array .from (new Set( ... ))包装器，用于在字符串包含重复字符的情况下删除重复项。如果没有这个，"aba"返回["aba", "aab", "baa", "baa", "aab", "aba"] 。有了它，我们得到["aba", "aab", "baa"] ，这更有意义。但这与我们的递归问题不同。

清理后的函数如下所示:

function permutations (str) {
  return (str .length <= 1) 
    ? [str] 
    : 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')

我们的基本情况非​​常简单，str.length <= 1 。在这种情况下，我们得到 [str] 。这只有两种可能:字符串为空，我们返回 [''] ，或者字符串只有一个字符，例如 'x' ，我们返回 ['x'] 。这些显然是正确的，因此我们继续进行递归调用。

假设我们通过了 'abc' 。 split和map调用将其转换为等价的:

[
  permutations ('bc') .map (p => 'a' + p), 
  permutations ('ac') .map (p => 'b' + p),
  permutations ('ab') .map (p => 'c' + p),
]

但是我们假设我们的递归适用于 'bc' 的较小字符串。 , 'ac' ，和'ab' 。这意味着permutations('bc')将产生['bc', 'cb'] ，其他的也类似，所以这相当于

[
  ['bc', 'cb'] .map (p => 'a' + p), 
  ['ac', 'ca'] .map (p => 'b' + p),
  ['ab', 'ba'] .map (p => 'c' + p),
]

这是

[
  ['abc', 'acb']
  ['bac', 'bca']
  ['cab', 'cba']
]

现在我们做reduce调用，它将每个数组连续连接到前一个结果，从 [] 开始，得到

['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

有一种更简洁的方法可以做到这一点。我们可以替换map调用后跟此 reduce调用单flatMap调用，如下所示:

function permutations (str) {
  return (str .length <= 1) 
    ? [str] 
    : str 
        .split ('')
        .flatMap ((char, i) => 
          permutations (str .substr (0, i) + str.substr (i + 1))
            .map (p => char + p)
        ) 
}

无论如何，我们已经展示了我们的归纳技巧。通过假设这适用于更简单的情况，我们表明它适用于当前的情况。 (不，我们还没有严格地做到这一点，只是通过示例，但是用某种数学严谨性来证明这一点并不是非常困难。)当我们将其与它适用于基本情况的演示结合起来时，我们证明它适用于所有情况。这取决于我们的递归调用在某种程度上更简单，最终导致基本情况。在这里，传递给递归调用的字符串比我们提供的字符串短一个字符，因此我们知道最终我们将达到str .length <= 1。健康)状况。因此我们知道它是有效的。

如果添加 Array .from (new Set ( ... ))包装器重新打开，这也适用于具有重复字符的情况。

---

¹您可能遇到过归纳法，也可能没有遇到过，您可能记得也可能不记得，但从本质上讲，它非常简单。这是一个非常简单的数学归纳论证:

We will prove that 1 + 2 + 3 + ... + n == n * (n + 1) / 2, for all positive integers, n.

First, we can easily see that it's true when n is 1: 1 = 1 * (1 + 1) / 2

Next we assume that the statement is true for all integers below n.

We show that it's true for n like this:

1 + 2 + 3 + ... + n is the same as 1 + 2 + 3 + ... + (n - 1) + n, which is (1 + 2 + 3 + ... (n - 1)) + n. But we know that the statement is true for n - 1 (since we assumed it's true for all integers below n), so 1 + 2 + 3 + ... + (n - 1) is, by substituting in n - 1 for n in the expression above, equal to (n - 1) * ((n - 1) + 1) / 2, which simplifies to (n - 1) * n / 2. So now our larger expression ((1 + 2 + 3 + ... (n - 1)) + n is the same as ((n - 1) * n / 2) + n, which we can simplify to (n^2 - n) / 2 + n and then to (n^2 - n + (2 * n)) / 2 and to (n^2 + n) / 2. which factors into n * (n + 1) / 2.

So, by assuming it's true for everything less than n we show that it's true for n as well. Together with the fact that it's true when n is 1, the principle of induction says that it's true for all positive integers n.

You may have seen induction stated slightly differently: If (a) it's true for 1 and (b) being true for n - 1 implies that it's true for n, then (c) it's true for all positive integers n. (The difference here is that we don't need the assumption that it's true for all integers below n, only for n - 1.) It's easy to prove the equivalence of these two models. And the everything below formulation usually makes for a more convenient analogy in recursive problems.