Función de inversión de cadena recursiva en javascript?

Question

Soy un ingeniero de frontend bastante experimentado con un fondo de CS débil. Estoy tratando de entender el concepto de recursión. La mayoría de los ejemplos y supuestas explicaciones que puedo encontrar simplemente no lo estoy explicando de una manera que sea fácil de entender.

Me he propuesto la tarea de escribir una función que invierta una cadena recursivamente. Sé que tiene que haber una condición básica (es decir, se encuentra la solución), pero no puedo entender cómo escribir algo así y podría usar una demostración para estudiar.

¿Alguien podría proporcionar una función de muestra?

Answer 1

Algo así como:

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

Así que la función es recursiva, ya que llama a sí mismo para hacer el trabajo.

Answer 2

Esta es una implementación bastante simple de C# del algoritmo que solicitó. Creo que podría reescribirse en Javascript con bastante facilidad.

/* 
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(); 
    } 
} 

Answer 3

Prueba esto:

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 4

Una versión recursiva cola, sólo por diversión (a pesar de que JavaScript no realiza la eliminación llamada de cola):

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

Answer 5

Es prolijo, pero me gusta hacer que sea fácil de entender en los pasos lógicos:

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 

}

Entonces llamar así:

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

Answer 6

Hasta ahora el mejor pienso:

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

Answer 7

una línea de código usando operadores ternarios se puede revertir fácilmente.

Explicación: si la cadena existe (si no es nula), entonces regrese la recursión; de lo contrario, detenga la recursión.

function reverseString(str) { 
    return (str ? reverseString(str.substring(1)) + str.charAt(0) : str); 
    } 

función de llamada:

console.log(reverseString('hello')); 

Answer 8

Una función 25% más rápido: 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");