如何遞歸地反轉字符串

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