小贝子编程

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



我如何在使用递归时编写相同的代码，我用迭代方法做到了，如果有人可以帮助我使用递归编码，我将不胜感激谢谢！ 这是我的代码：

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

一系列重构

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

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的状态。 这使得它更难理解。 让我们更改它以使checkForPalindrome返回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，我们可以注意到它现在是一个有用的函数来确定一个字符串是否是一个回文。 因此，我们不妨将其从主要功能的内脏中拉出来，使其独立运行。

但是返回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")，并计算回文的数量。 如果单词的长度少于两个字符，那么它没有回文，我们返回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"。 请注意，有些人憎恶这个想法。 这可能包括您的教练，所以要小心。 (如果有人反对，你可以随时向他们指出一篇关于这个想法的文章，描述性变量名称：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"));

做所有递归的事情

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

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

相关内容

最新更新


热门标签：

javascript python java c# php android html jquery c++ css ios sql mysql arrays asp.net json python-3.x ruby-on-rails .net sql-server django objective-c excel regex ruby linux ajax iphone xml vba spring asp.net-mvc database wordpress string postgresql wpf windows xcode bash git oracle list vb.net multithreading eclipse algorithm macos powershell visual-studio image forms numpy scala function api selenium