Funzione di inversione stringa ricorsiva in javascript?

Question

Sono un ingegnere frontend piuttosto esperto con uno sfondo CS debole. Sto cercando di capire il concetto di ricorsione. La maggior parte degli esempi e delle presunte spiegazioni che riesco a trovare non lo spiegano in un modo che trovo facile da capire.

Mi sono impostato per scrivere una funzione che invertirà una stringa in modo ricorsivo. So che ci deve essere una condizione di base (cioè la soluzione è stata trovata), ma non riesco a capire come effettivamente scrivere qualcosa di simile e potrei usare una demo per studiare.

Qualcuno potrebbe fornire una funzione di esempio?

Answer 1

Qualcosa di simile:

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

Quindi la funzione è ricorsiva in quanto si definisce per fare il lavoro.

Answer 2

Questa è un'implementazione C# piuttosto semplice dell'algoritmo che hai richiesto. Penso che potrebbe essere riscritto in javascript abbastanza facilmente.

/* 
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

Prova questo:

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 versione ricorsiva di coda, solo per calci (anche se JavaScript non esegue l'eliminazione chiamata coda):

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

E 'prolisso, ma mi piace fare facile capire in fasi logiche:

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 

}

quindi chiamare le cose come:

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

Answer 6

Finora il miglior penso:

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

Answer 7

Una linea di codice utilizzando operatori ternari si può facilmente invertire tale tendenza.

Spiegazione: se la stringa esiste (se non è nulla), restituisce la ricorsione altrimenti interrompe la ricorsione.

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

chiamata di funzione:

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

Answer 8

Una funzione del 25% più veloce: 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");