JavaScript中的递归字符串反转函数？

Question

我是一位经验丰富的前端工程师，计算机科学背景较弱。我正在尝试理解递归的概念。我能找到的大多数例子和所谓的解释都没有以我认为容易理解的方式解释。

我给自己设定了一个任务，编写一个函数来递归地反转字符串。我知道必须有一个基本条件（即找到解决方案），但我不知道如何实际编写这样的东西，并且可以使用演示来研究。

有人可以提供示例功能吗？

Answer 1

类似于：

function reverse (str) {
    if (str === "") {
        return "";
    } else {
        return reverse(str.substr(1)) + str.charAt(0);
    }
}

所以该函数是递归的，因为它调用自身来完成工作。

Answer 2

尾递归版本，只是为了好玩（即使 JavaScript 不执行尾调用消除）：

function reverse(str) {
  function r(s, acc) {
    return (s.length == 0) ? acc : r(s.substr(1), s.charAt(0) + acc);
  };
  return r(str, '');
};

Answer 3

使用布尔运算符的一行代码。

说明：如果字符串存在，则调用递归来减少字符串，否则回退到不存在的字符串（最后一次递归调用）

  function reverseString(s) {
    return s && reverseString(s.slice(1)) + s[0] || s;
  }

Answer 4

速度提高 25% 的函数：jsperf.com

function Reverse(str) {
  if (str === null) {
    return null;
  }
  if (str.length <= 1) {
    return str;
  }
  var first = str[0];
  var last = str[str.length - 1];
  var str1 = Reverse(str.substring(1, str.length - 1));
  return last + str1 + first;
}

var result = Reverse("a really serious string of nothingness making call stack to explode");

Answer 5

function reverse(str) {
  if(str.charAt(0) === ''){
    return "";
  }
  return str.charAt(str.length -1) + reverse(str.substring(0,str.length-1));
}

Answer 6

//以字符串作为参数调用该函数

function strrev(str) {
    return str.length !== 1 ? strrev(str.slice(1))+str[0] : str;
}

Answer 7

根据 MDN Web 文档 ，您应该使用 substring() 而不是 substr()：

警告：虽然 String.prototype.substr(…) 并未被严格弃用（如“从 Web 标准中删除”），但它被视为遗留函数并应尽可能避免。它不是核心 JavaScript 语言的一部分，将来可能会被删除。如果可能的话，请使用 substring() 方法代替。

此外，如果没有提供索引作为 charAt()，默认为0。

因此，我们可以编写一个递归单行代码来使用 三元运算符 并应用上述逻辑：

const reverse_string = s => s === '' ? '' : reverse_string(s.substring(1)) + s.charAt();

console.log(reverse_string('Hello, world!')); // !dlrow ,olleH

Answer 8

我用于退出递归的基本情况是当长度减少到 0 时

在每个递归调用中我们将取出字符串的最后一个字符并将其附加到我们从字符串的递归调用中获得的结果，由于使用切片删除了最后一个字符，因此其尺寸较小。

function reverse(str){
 if(str.length===0)
    return "";

return str[str.length-1]+reverse(str.slice(0,str.length-1));
}

Answer 9

您还可以使用下面的代码通过递归简单反转字符串

const reverseIt = (x) => {
    if (x === "") {
      return "";
    }
    return x[x.length - 1] + reverseIt(x.substring(0, x.length - 1));
};

Answer 10

我是这样解决的：

function reverse(s) {
  const index = s.indexOf(" "); 
  if(index === -1) {
    return s
  }
  else { 
      return reverse(s.slice(index+1)) + " " + s.slice(0,index)
  }
} 

Answer 11

另一个解决方案：

function reverse(str, newStr = "") {
  // Base case
  if (str.length === 0) return newStr;
  // newStr += str.slice(-1)
  return reverse(str.slice(0, -1), newStr += str.slice(-1));
  }
  
  console.log(reverse("house")) // esuoh

Answer 12

另一种使用默认参数的解决方案：

function reverse(str, newStr = "") {
  // Base case
  if (str.length === 0) return newStr;
  
  return reverse(str.slice(0, -1), newStr += str.slice(-1));
  }
  
  console.log(reverse("house")) // esuoh

Answer 13

let fruit = "APPLE";

function reverseStringByRecursion(name) {
  if (name.length == 0) {
    return "";
  } else {
    let lastChar = name[name.length - 1];
    let excludingLastChar = name.slice(0, name.length - 1);
    return lastChar + reverse(excludingLastChar);
  }
}

var reversedString = reverseStringByRecursion(fruit);
console.log("Reversed string:", reversedString);

Answer 14

到目前为止我认为最好的：

function reverse(s) {
    if (s.length===1) return s;
    return reverse(s.slice(1)) + s[0];
}

Answer 15

试试这个：

function recurse(s) {  
  if (s.length == 0) {  
    return '' // stopping condition  
  } else {  // return last char + result of function called with chars up to last char  
    return s.substring(s.length, s.length -1) + recurse(s.substring(0, s.length -1))  
  }
}  

Answer 16

它很冗长，但我喜欢以逻辑步骤使其易于理解：

function rev(soFar, count){
   console.log("asString: " + soFar );
   console.log("count: " + count);
   var len = soFar.length;
   var ret = soFar;//ret needs to be a reference to soFar
   if(len > count){
      var subd = soFar.substring(1,len);
      var first = soFar[0];
      //we want to inject the first letter at the index position one back from the length, minus what the count is at this point
      var indexOfInsert = len-1 - count;//so if count is 0 and length is 5, we want 4 (4 -0)
      var asArray = subd.split("");
      asArray.splice(indexOfInsert,0,first);
      count++;//need to increment count for the next round
      var asString = "";
    //recreate as string, not array - the default toString() makes this a comma delimited string. It is best toi just recreate it in a loop
    for(var i = 0; i<len; i++){
        asString+=asArray[i];
    }
    ret = rev(asString,count);//ret always needs to be reassigned
}
//only get here when count is greater than the length of the original string
return ret;//will always be a reference to soFar, which is being reassigned in the recursive loop

}

然后这样称呼它：

var reversed = rev("Hello",0);
console.log("result",reversed);

Answer 17

这是您所要求的算法的非常简单的 C# 实现。
我认为它可以很容易地用 JavaScript 重写。

/*
C#: The Complete Reference 
by Herbert Schildt 

Publisher: Osborne/McGraw-Hill (March 8, 2002)
ISBN: 0072134852
*/


// Display a string in reverse by using recursion. 

using System; 

class RevStr { 

  // Display a string backwards. 
  public void displayRev(string str) { 
    if(str.Length > 0)  
      displayRev(str.Substring(1, str.Length-1)); 
    else  
      return; 

    Console.Write(str[0]); 
  } 
} 

public class RevStrDemo { 
  public static void Main() {   
    string s = "this is a test"; 
    RevStr rsOb = new RevStr(); 

    Console.WriteLine("Original string: " + s); 

    Console.Write("Reversed string: "); 
    rsOb.displayRev(s); 

    Console.WriteLine(); 
  } 
}