如何从迭代方法编写递归函数？

Question

我如何在使用递归的同时编写下面的相同代码，我是用迭代方法完成的，如果有人能帮助我使用递归编写代码，我将不胜感激谢谢！这是我的代码：

function returnNumberOfPalindromes(word) {
  function checkForPalindrome(chunk) { 
    let chunkArray = [];
    for (const letter of chunk) { 
      chunkArray.push(letter);
    }
    if (chunkArray.reverse().join('') === chunk) {
      tally += 1;
    }
  }
  let tally = 0;

  for (let index1 = 0, index2 = 2; index1 <= word.length; index1++, (index2 = index1 + 2)) {
    for (; index2 <= word.length; index2++) { 
      let chunk = word.slice(index1, index2); 
      checkForPalindrome(chunk);
    }
  }
  console.log(tally);
}

returnNumberOfPalindromes("kayak");
returnNumberOfPalindromes("aya");
returnNumberOfPalindromes("appal");
returnNumberOfPalindromes("addadaadd");

Answer 1

我不打算递归地编写 checkForPalindrome，因为这样做很简单：

function checkForPalindrome(str) {
  // we can use .split("") to convert to an array of characters
  return str.split("").reverse().join("") == str;
}

function palindromesAtStart(str) {
  // lengths 0 and 1 can't be palindromes
  if (str.length < 2) {
    return 0;
  }
  // if it's a palindrome add 1
  const diff = checkForPalindrome(str) ? 1 : 0;
  // now shorten the string and check again
  return diff + palindromesAtStart(str.slice(0, -1));
}

function returnNumberOfPalindromes(str) {
  if (str.length < 2) {
    return 0;
  }
  // total palindromes is palindromes at start plus palindromes not at start
  return palindromesAtStart(str) + returnNumberOfPalindromes(str.slice(1));
}


console.log(returnNumberOfPalindromes("kayak"));
console.log(returnNumberOfPalindromes("aya"));
console.log(returnNumberOfPalindromes("appal"));
console.log(returnNumberOfPalindromes("addadaadd"));

本质上，字符串中的回文可以包含第一个索引，也可以不包含第一个索引。因此，我们可以编写一个简单的递归函数（palindromesAtStart）来计算包含第一个索引的回文数，并将其添加到不包含第一个索引的回文数。

Answer 2

一系列重构

经过一系列的重构，我们将得到以下代码：

const isPalindrome = (s) =>  
  s.length == 0 ? true : s[0] === s[s.length - 1] && isPalindrome(s.slice(1, -1))

const countPalindromicPrefixes = (s) =>
  s.length < 2 ? 0 : (isPalindrome(s) ? 1 : 0) + countPalindromicPrefixes(s.slice (0, -1)) 

const countPalindromes = (s) => 
  s.length < 2 ? 0 : countPalindromicPrefixes(s) + countPalindromes(s.slice(1))


console .log (countPalindromes ("kayak"));
console .log (countPalindromes ("aya"));
console .log (countPalindromes ("appal"));
console .log (countPalindromes ("addadaadd"));
console .log (countPalindromes ("madamimadam"));

每个步骤都有一个片段（默认情况下隐藏，所以这不是太长）表明我们到目前为止还没有破坏任何东西。

起点

初始代码如下所示：

function returnNumberOfPalindromes(word) {
  function checkForPalindrome(chunk) { 
    let chunkArray = [];
    for (const letter of chunk) { 
      chunkArray.push(letter);
    }
    if (chunkArray.reverse().join('') === chunk) {
      tally += 1;
    }
  }
  let tally = 0;

  for (let index1 = 0, index2 = 2; index1 <= word.length; index1++, (index2 = index1 + 2)) {
    for (; index2 <= word.length; index2++) { 
      let chunk = word.slice(index1, index2); 
      checkForPalindrome(chunk);
    }
  }
  console.log(tally);
}

function returnNumberOfPalindromes(word) {
  function checkForPalindrome(chunk) { 
    let chunkArray = [];
    for (const letter of chunk) { 
      chunkArray.push(letter);
    }
    if (chunkArray.reverse().join('') === chunk) {
      tally += 1;
    }
  }
  let tally = 0;

  for (let index1 = 0, index2 = 2; index1 <= word.length; index1++, (index2 = index1 + 2)) {
    for (; index2 <= word.length; index2++) { 
      let chunk = word.slice(index1, index2); 
      checkForPalindrome(chunk);
    }
  }
  console.log(tally);
}

returnNumberOfPalindromes("kayak");
returnNumberOfPalindromes("aya");
returnNumberOfPalindromes("appal");
returnNumberOfPalindromes("addadaadd");

修复 `for`-循环

将内循环的初始索引作为外循环增量的一部分进行更新是非常奇怪的。这更常见，我敢说，更合乎逻辑：

  for (let index1 = 0; index1 <= word.length; index1++) {
    for (let index2 = index1 + 2; index2 <= word.length; index2++) { 
      let chunk = word.slice(index1, index2); 
      checkForPalindrome(chunk);
    }
  }

function returnNumberOfPalindromes(word) {
  function checkForPalindrome (chunk) { 
    if (chunk.split('').reverse().join('') === chunk) {
      tally += 1;
    }
  }
  let tally = 0;

  for (let index1 = 0; index1 <= word.length; index1++) {
    for (let index2 = index1 + 2; index2 <= word.length; index2++) { 
      let chunk = word.slice(index1, index2); 
      checkForPalindrome(chunk);
    }
  }
  console.log(tally);
}

returnNumberOfPalindromes("kayak");
returnNumberOfPalindromes("aya");
returnNumberOfPalindromes("appal");
returnNumberOfPalindromes("addadaadd");
returnNumberOfPalindromes("madamimadam");

简化`checkForPalindrome`

checkForPalindrome 中所做的大部分工作都是不必要的。 String.prototype.split 已经将字符串转换为字符数组。所以我们可以将该部分更改为：

  function checkForPalindrome (chunk) { 
    if (chunk.split('').reverse().join('') === chunk) {
      tally += 1;
    }
  }

function returnNumberOfPalindromes(word) {
  function checkForPalindrome (chunk) { 
    if (chunk.split('').reverse().join('') === chunk) {
      tally += 1;
    }
  }
  let tally = 0;

  for (let index1 = 0; index1 <= word.length; index1++) {
    for (let index2 = index1 + 2; index2 <= word.length; index2++) { 
      let chunk = word.slice(index1, index2); 
      checkForPalindrome(chunk);
    }
  }
  console.log(tally);
}

returnNumberOfPalindromes("kayak");
returnNumberOfPalindromes("aya");
returnNumberOfPalindromes("appal");
returnNumberOfPalindromes("addadaadd");
returnNumberOfPalindromes("madamimadam");

使局部函数成为纯函数

我们的内部函数 checkForPalindrome 没有 return 值。相反，它正在更新 tally 的状态。这使得它更难理解。让我们将其更改为 checkForPalindrome return true 或 false，并根据该结果更新 tally：

  function checkForPalindrome (chunk) { 
    return chunk.split('').reverse().join('') === chunk
  }

      if (checkForPalindrome(chunk)) {
        tally += 1
      }

function returnNumberOfPalindromes(word) {

  function checkForPalindrome (chunk) { 
    return chunk.split('').reverse().join('') === chunk
  }

  let tally = 0;

  for (let index1 = 0; index1 <= word.length; index1++) {
    for (let index2 = index1 + 2; index2 <= word.length; index2++) { 
      let chunk = word.slice(index1, index2); 
      if (checkForPalindrome(chunk)) {
        tally += 1
      }
    }
  }
  console.log(tally);
}

returnNumberOfPalindromes("kayak");
returnNumberOfPalindromes("aya");
returnNumberOfPalindromes("appal");
returnNumberOfPalindromes("addadaadd");
returnNumberOfPalindromes("madamimadam");

拉出那个内部函数

仍然关注 checkForPalindrome，我们可以注意到它现在是一个有用的函数来确定一个字符串是否是回文。所以我们不妨把它从我们的主要功能中拉出来，让它独立出来。

但是函数 returning true 或 false 的常见约定是以 is 开头命名它。在这种情况下，isPalindrome 绝对更有意义。所以我们改成这样：

function isPalindrome (word) { 
  return word.split('').reverse().join('') === word
}

和

      if (isPalindrome(chunk)) {
        tally += 1
      }

function isPalindrome (word) { 
  return word.split('').reverse().join('') === word
}

function returnNumberOfPalindromes(word) {

  let tally = 0;

  for (let index1 = 0; index1 <= word.length; index1++) {
    for (let index2 = index1 + 2; index2 <= word.length; index2++) { 
      let chunk = word.slice(index1, index2); 
      if (isPalindrome(chunk)) {
        tally += 1
      }
    }
  }
  return tally;
}

console .log (returnNumberOfPalindromes("addadaadd"));  //=> 7

将此递归化

现在迈出了重要的一步。我们想让这个递归。让我们检查一下我们的主循环在做什么：

  for (let index1 = 0; index1 <= word.length; index1++) {
    for (let index2 = index1 + 2; index2 <= word.length; index2++) { 
      let chunk = word.slice(index1, index2); 
      if (isPalindrome(chunk)) {
        tally += 1
      }
    }
  }

此代码在索引中循环两次，找到从索引 0 开始的所有子字符串，然后所有从索引 1 开始的子字符串，然后所有从索引 2 开始的子字符串，等等。对于每个子字符串，它都会测试字符串是否为回文，如果是，我们增加计数。

这种双循环几乎肯定意味着我们也在进行双递归。所以我们可以认为它有两个功能。

一个函数接受一个字符串并查看该字符串的所有前缀（例如“goat”，前缀为“goat”、“goa”、“go”和“g”）并计数那些是回文的数量。如果单词的长度少于两个字符，则它没有回文，我们 return 0，否则我们包括 1 如果单词是回文， 0 如果它不是并将其添加到递归调用的结果中，该调用删除了最后一个字符：

function returnNumberOfPalindromicPrefixes(word) {
  if (word .length < 2) {
    return 0
  }
  return (isPalindrome(word) ? 1 : 0) + returnNumberOfPalindromicPrefixes(word.slice(0, -1)) 
}

第二个函数在字符串的开头处重复出现。同样，如果单词长度少于两个字符，我们再次 return 0。否则我们将调用前缀函数的结果添加到对通过删除第一个字符形成的字符串的递归调用：

function returnNumberOfPalindromes(word) {
  if (word .length < 2) {
    return 0
  }
  return returnNumberOfPalindromicPrefixes(word) + returnNumberOfPalindromes(word.slice(1))
}

function isPalindrome(word) { 
  return word.split('').reverse().join('') === word
}

function returnNumberOfPalindromicPrefixes(word) {
  if (word .length < 2) {
    return 0
  }
  return (isPalindrome(word) ? 1 : 0) + returnNumberOfPalindromicPrefixes(word.slice(0, -1)) 
}

function returnNumberOfPalindromes(word) {
  if (word .length < 2) {
    return 0
  }
  return returnNumberOfPalindromicPrefixes(word) + returnNumberOfPalindromes(word.slice(1))
}

console .log (returnNumberOfPalindromes("kayak"));
console .log (returnNumberOfPalindromes("aya"));
console .log (returnNumberOfPalindromes("appal"));
console .log (returnNumberOfPalindromes("addadaadd"));
console .log (returnNumberOfPalindromes("madamimadam"));

插曲

至此我们有了合理的代码。我们已经将其重构为逻辑相当清晰的递归函数。（和Applet123的回答也很相似。）

这对您（或您的导师）来说可能足够了。

但我认为还有更多有用的更改需要进行。将接下来的几个步骤视为可有可无的步骤。

函数命名

这听起来可能微不足道，但名字 returnNumberOf<Whatever> 却非常可怕。 count<Whatever>、numberOf<Whatever> 可能会更好 sizeOf<Whatever>.

我会选择第一个，它会给我们名字countPalindromicPrefixes和countPalindromes。

function isPalindrome (word) { 
  return word.split('').reverse().join('') === word
}

function countPalindromicPrefixes(word) {
  if (word .length < 2) {
    return 0
  }
  return (isPalindrome(word) ? 1 : 0) + countPalindromicPrefixes(word.slice(0, -1)) 
}

function countPalindromes(word) {
  if (word .length < 2) {
    return 0
  }
  return countPalindromicPrefixes(word) + countPalindromes(word.slice(1))
}

console .log (countPalindromes("kayak"));
console .log (countPalindromes("aya"));
console .log (countPalindromes("appal"));
console .log (countPalindromes("addadaadd"));
console .log (countPalindromes("madamimadam"));

更现代的 JS

使用箭头函数而不是函数声明可以清理大量代码。 Conditional (ternary) operators 也行。使用这些我们可以变成这样：

function countPalindromes(word) {
  if (word .length < 2) {
    return 0
  }
  return countPalindromicPrefixes(word) + countPalindromes(word.slice(1))
}

进入这个：

const countPalindromes = (word) => 
  word .length < 2 ? 0 : countPalindromicPrefixes(word) + countPalindromes(word.slice(1))

并对其他功能做类似的事情。

const isPalindrome = (word) =>  
  word.split('').reverse().join('') === word

const countPalindromicPrefixes = (word) =>
  word.length < 2 ? 0 : (isPalindrome(word) ? 1 : 0) + countPalindromicPrefixes(word.slice(0, -1)) 

const countPalindromes = (word) => 
  word.length < 2 ? 0 : countPalindromicPrefixes(word) + countPalindromes(word.slice(1))


console .log (countPalindromes ("kayak"));
console .log (countPalindromes ("aya"));
console .log (countPalindromes ("appal"));
console .log (countPalindromes ("addadaadd"));
console .log (countPalindromes ("madamimadam"));

参数命名

我们在这里为函数使用参数名称“word”。但我们真的意味着这是一个词吗？一句话“一个人，一个计划，一条运河：巴拿马！”被广泛描述为回文。（虽然它不适合我们的测试，但我们可以通过在执行当前测试之前将值小写并删除任何非字母字符来轻松修复它。）事实上，我向这些添加了一个测试用例，它捕获另一个 classic 回文的版本，“女士，我是亚当。”

所以输入可以是一个词或一个句子？也许也是一个短语？人们有时会谈论数字是回文数字，例如 2112。因此“单词”不是这些数字的正确名称。我们的似乎采用任意字符串。所以我们应该将参数重命名为捕获它的东西。也许是“str”？也许是“字符串”？我要提出一些更激进的建议。我们真的不知道类型，而且它是一个单行函数，所以一个仍然给人一种“字符串”味道的单字符名称在这里似乎是完全合理的。我会选择“s”。请注意，有些人讨厌这个想法。这可能包括你的导师，所以要小心。（如果有人反对，你总是可以让他们看到一篇关于这个想法的文章，Descriptive Variable Names: A Code Smell，作者 John DeGoes。但他们可能仍然会开始向你扔东西，所以要小心。）

所以我们可以这样写：

const countPalindromicPrefixes = (s) =>
  s.length < 2 ? 0 : (isPalindrome(s) ? 1 : 0) + countPalindromicPrefixes(s.slice(0, -1))

const isPalindrome = (s) =>  
  s.split('').reverse ().join('') === s

const countPalindromicPrefixes = (s) =>
  s.length < 2 ? 0 : (isPalindrome(s) ? 1 : 0) + countPalindromicPrefixes(s.slice(0, -1)) 

const countPalindromes = (s) => 
  s.length < 2 ? 0 : countPalindromicPrefixes(s) + countPalindromes(s .slice(1))


console .log (countPalindromes ("kayak"));
console .log (countPalindromes ("aya"));
console .log (countPalindromes ("appal"));
console .log (countPalindromes ("addadaadd"));
console .log (countPalindromes ("madamimadam"));

做所有事情递归

除了 class 作业外，我不会执行以下操作。我们已经有了 isPalindrome 的工作版本，一个可读且高效的版本。但由于这显然是一个递归赋值，因此也可以编写 isPalindrome 的递归版本。

为此，我们可以递归地考虑这个问题，注意如果第一个和最后一个字符匹配并且中间的字符串也是回文，则字符串是回文。空字符串在这里被认为是回文，单字符字符串也是如此。（在这种情况下，第一个和最后一个字符指向同一个地方，所以它们当然是相同的。）我们可以这样写：

const isPalindrome = (s) =>  
  s.length == 0 ? true : s[0] === s[s.length - 1] && isPalindrome(s.slice(1, -1))

请注意，对于这里的一般问题，我们没有将 1 个字符的子字符串视为回文，但在主要函数中处理了。 isPalindrome 高兴地报告它们，这似乎很合适。

const isPalindrome = (s) =>  
  s.length == 0 ? true : s[0] === s[s.length - 1] && isPalindrome(s.slice(1, -1))

const countPalindromicPrefixes = (s) =>
  s.length < 2 ? 0 : (isPalindrome(s) ? 1 : 0) + countPalindromicPrefixes(s.slice (0, -1)) 

const countPalindromes = (s) => 
  s.length < 2 ? 0 : countPalindromicPrefixes(s) + countPalindromes(s.slice(1))


console .log (countPalindromes ("kayak"));
console .log (countPalindromes ("aya"));
console .log (countPalindromes ("appal"));
console .log (countPalindromes ("addadaadd"));
console .log (countPalindromes ("madamimadam"));

如何从迭代方法编写递归函数？

How to code an recursion function from an iterative approach?

javascript

recursion

iterator

function

palindrome

一系列重构

起点

修复 `for`-循环

简化`checkForPalindrome`

使局部函数成为纯函数

拉出那个内部函数

将此递归化

插曲

函数命名

更现代的 JS

参数命名

做所有事情递归

如何从迭代方法编写递归函数？

How to code an recursion function from an iterative approach?

javascript

recursion

iterator

function

palindrome

一系列重构

起点

修复 for-循环

简化checkForPalindrome

使局部函数成为纯函数

拉出那个内部函数

将此递归化

插曲

函数命名

更现代的 JS

参数命名

做所有事情递归

修复 `for`-循环

简化`checkForPalindrome`