如何递归地反转字符串

Question

我前几天正在接受采访，并被要求编写一个递归地反转字符串的方法。

我开始写一个自己调用并卡住的方法。

这是我被问到的问题，在JavaScript中递归地反转字符串“Obama”。

这是我得到了多少。

function reverseString(strToReverse) 
{ 

     reverseString(strToReverse); 

}; 

卡住了，他们说没有i循环。

任何人有任何想法？

Answer 1

见the solution by @MaxZoom below一个更简洁的版本。

请注意，由于JS解释器不需要执行尾部调用消除，所以我自己的答案中的尾递归样式与简单递归版本相比没有优势。

[原文]

这里的一个尾递归版本，通过从输入字符串的前去除的字符，并将其预先考虑到“累加器”串的前工作的：

function reverse(s, acc) { 
    if (s.length <= 0) { return acc; } 
    return reverse(s.slice(1), s.charAt(0) + (acc||'')); 
} 

reverse('foobar'); // => "raboof" 

Answer 2

看看这样说：颠倒字符串将与原来的最后一个字母，然后是所有但最后一个字母开始，逆转。

所以：

function reverseString(strToReverse) 
{ 
    if (strToReverse.length <= 1) 
    return strToReverse; 

    // last char + 
    // 0 .. second-last-char, reversed 
    return strToReverse[strToReverse.length - 1] + 
    reverseString(strToReverse.substring(0, strToReverse.length - 1)); 
} 

Answer 3

不扭转一个字符串的最聪明的方式，但它是递归：

function reverse(input, output) { 
    output = output || ''; 
    if (input.length > 0) { 
     output = output.concat(input[input.length -1]); 
     return reverse(input.substr(0, input.length - 1), output); 
    } 
    return output; 
} 

console.log(reverse('Obama')); 

这里有一个jsfiddle

Answer 4

如果字符串为空或单个字符，保持不变。 否则，

1. 删除第一个字符。
2. 反转剩余的字符串。
3. 将上面的第一个字符添加到反转字符串。

4. 返回新的字符串。

   function reverse(str) 
   { 
       if (str.length <= 1) 
       return str; 
   
       else 
       return str[str.length - 1] + reverse(str.substring(0, str.length - 1)); 
   } 
   

Answer 5

也许这样的事情？

var base = 'Obama', 
    index = base.length, 
    result = ''; 

function recursive(){ 
    if (index == 0) return; 
    index -= 1; 
    result += base[index]; 
    recursive(); 
} 

recursive(); 

alert(result); 

的jsfiddle： https://jsfiddle.net/hy1d84jL/

编辑：你能想到的递归为无限for..loop。让我们以“受控”的方式使用它，并定义边界--0为最小值，Obama字的长度为最大值。现在，让我们调用它自己的任意次数，然后按照需要进行操作以反转字符串，即 - 将index变量递减1，并从末尾对字符进行求和。希望能帮助到你。很好的问题。

Answer 6

如果函数只能有单个输入我将字符串分割成小片，并以相反的顺序添加它们放在一起

​​

Answer 7

最简单的一个：

function reverse(input) { 
 
    if (input==null || input.length < 2) return input; 
 
    return reverse(input.substring(1)) + input.charAt(0); 
 
} 
 

 
console.log(reverse('Barack Obama'));

Answer 8

单线解决方案。如果他们问我告诉他们它在本地代码部分是递归的，而不是问任何更愚蠢的问题。

var result = "Obama".split('').reverse().join(''); 

输出： amabO

Answer 9

这里真正的问题不是“如何反转一个字符串”。真正的问题是，“你理解递归”。这就是面试问题所在！

所以，为了解决这个问题，你需要告诉你知道递归是关于什么的，而不是你可以反转字符串“Obama”。如果你需要做的只是扭转字符串“奥巴马”，你可以写return "amabO";见？

换句话说，这个特定的编程任务不是它的全部内容！真正的解决方案不是复制和粘贴来自答案的代码，而是了解递归。

简言之，

• 递归涉及再次调用同一个功能，是的，但是这还不是全部
• 为了防止堆栈溢出，你必须确保函数不调用自身无限
• 因此，总是有一个条件下，该功能可以退出，而无需调用自己（再次）
• 当它确实再次调用自己，它应该这样做的参数，使上述条件更有可能。

在字符串操作的情况下，一种方法是确保它只使用比它所调用的字符串更短的字符串来调用它自己。由于字符串的长度不是无限长，所以函数不能以这种方式调用自己无限次数。所以条件可能是该字符串的长度为零，在这种情况下，不可能使用较短的字符串来调用它自己。

如果你能证明你知道所有这些，并且可以在真实世界的程序中使用它，那么你就可以通过面试了。如果您复制并粘贴您在互联网上找到的某些源，则不是。

希望这会有所帮助！

Answer 10

我们可以使用三元运算符

容易扭转的递归方法字符串

function reverseString(strToReverse) { 

    return str.length > 1 ? reverse(str.slice(1)) + str.charAt(0) : str; 
} 

reverseString("America");