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

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

一系列的重构

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

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没有返回值。相反，它正在更新 的状态tally。这使得它更难理解。让我们将其更改为checkForPalindromereturntrue或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，我们可以注意到它现在是一个有用的函数来确定字符串是否是回文。因此，我们不妨将其从我们的主要功能中取出并使其独立。

true但返回or的函数的常见约定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”）并计算那些前缀的数量。是回文。如果单词长度少于两个字符，则它没有回文，我们返回0，否则我们包含1该单词是否是回文，0如果不是，则将其添加到删除最后一个字符的递归调用的结果中：

function returnNumberOfPalindromicPrefixes(word) {

  if (word .length < 2) {

    return 0

  }

  return (isPalindrome(word) ? 1 : 0) + returnNumberOfPalindromicPrefixes(word.slice(0, -1)) 

}

第二个函数在字符串的开头重复出现。同样，如果单词长度少于两个字符，我们再次返回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

使用箭头函数而不是函数声明可以清理大量代码。 条件（三元）运算符也可以。使用这些我们可以变成这样：

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”。但我们真的想让这成为一个词吗？这句话“一个人，一个计划，一条运河：巴拿马！” 被广泛描述为回文。（虽然它不适合我们的测试，但我们可以通过在执行当前测试之前降低值并删除任何非字母字符来轻松修复它。）事实上，我向其中添加了一个测试用例，它捕获另一个经典回文的版本“女士，我是亚当”。

那么输入可以是一个单词或一个句子？也许也是一个短语？人们有时会谈论数字是回文数，例如 2112。因此“单词”并不是这些数字的正确名称。我们的似乎采用任意字符串。因此，我们应该将参数重命名为捕获该参数的名称。也许是“str”？也许是“字符串”？我将提出一些更激进的建议。我们确实不知道类型，而且它是一个单行函数，因此仍然具有“字符串”风格的单字符名称在这里似乎完全合理。我会选择“s”。请注意，有些人厌恶这种想法。这可能包括你的教练，所以要小心。（如果有人反对，你可以随时向他们推荐一篇关于这个想法的文章，描述性变量名称：代码味道，约翰·德戈斯着。但他们可能仍然开始向你扔东西，所以要小心。）

所以我们可以这样写：

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"));

递归地做所有的事情

除了课堂作业之外，我不会做以下事情。我们已经有了 的一个工作版本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"));

Answer 2

我不会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）来计算包含第一个索引的回文数，并将其添加到不包含第一个索引的回文数中。