Umkehren einer Zeichenfolge mit Rekursion

Question

Ich bin in Rekursion und ich wollte eine einfache Sache tun, wie eine Zeichenfolge umzukehren. Die Funktion funktioniert, aber ich verstehe nicht, wie und das macht mich sehr frustriert. (Rekursiven Teil)

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

Sagen wir, ich habe eine Zeichenfolge „abcd“. So ist die erste Schleife wäre:

"myString.substr (1)" macht aus "abcd" -> "bcd" und dann "charAt (0)" bekommt "b "; Das Ergebnis wäre "bcd + b"? Oder wird "myString.charAt (0)" ausgeführt, wenn die Rekursion beendet ist?

Ich bin völlig verloren ... wie sieht die ganze Prozedur aus?

Answer 1

Nein, alle Parameter, die Sie an den rekursiven Aufruf übergeben, werden vor dem rekursiven Aufruf ausgewertet. (Klarstellung: das bedeutet nur myString.substr(1))

Sie sind richtig, myString.charAt(0) wird ausgeführt, nachdem Ihr rekursiver Aufruf zurückgegeben wird. Dies macht es komplexer als die sogenannte "Tail-Rekursion" oder "Kopfrekursion", bei der der rekursive Aufruf die letzte bzw. erste Operation in Ihrer rekursiven Funktion ist. Das Schreiben einer tailrekursiven oder kopfrekursiven Funktion kann bestimmten Compilern helfen, effizienteren Code zu erzeugen, und es hilft auch, Ihre Funktion verständlicher zu machen, aber es ist nicht "erforderlich".

Hier ist, wie es aussieht:

abcd 
bcd + a 
cd + ba 
d + cba 
dcba 

Answer 2

myString nicht geändert, wenn Sie die substr-Methode aufrufen. Diese

var mystring = 'abcd'; 
mystring.substr(1); 

console.log(mystring) // abcd 

bedeutet, dass jeder rekursive Aufruf rufen Sie eine brandneue String mit dem ersten Zeichen bis zum Ende der Schnur bewegt.

Erster Aufruf: recursiveString (bcd) + a

Zweiter Aufruf: recursiveString (cd) + b

Dritte Aufforderung: recursiveString (d) + c

Letzter Aufruf: recursiveString ("") + d

Erinnern Sie sich daran, dass jeder rekursive Aufruf ein Zeichen und dann eine Funktion zurückgibt, um mehr von ihnen abzurufen. Das bei jedem Aufruf zurückgegebene Zeichen erscheint nach der Funktion.

So baut die Funktion die Zeichenfolge wie: "" -> d -> c -> b -> a

Answer 3

„myString.substr (1)“macht von "ABCD" -> "bcd" und dann "charAt (0)" bekommt "b";

Nein, myString.substr(1) gibt einen neuen String mit dem Wert "bcd", den Wert von myString nicht ändert, so dass, wenn myString.charAt(0) der Wert genannt wird "a" zurückgegeben wird, weil es die ursprüngliche Zeichenfolge mit dem Wert indiziert "abcd"

Answer 4

Blick darauf, wie diese bewertet

Rückkehr Reverse (myString.substr (1)) + myString.charAt (0);
Schritt 1: zurückgeben reverseString ("bcd") + a;
Schritt 2: zurück reverseString ("cd") + b + a;
Schritt 3: zurück reverseString ("d") + c + b + a;
Schritt 4: zurück reverseString ("") + d + c + b + a;

Answer 5

Ich denke, es hilfreicher ist es in der Reihenfolge zu suchen, in dem die Dinge zurück von den (verschachtelten) rufen zu Reverse, da sie rief in Reverse hält, bis sie in einem leeren String geht - das ist der Punkt es fängt an, Dinge zurückzugeben.

call reverseString("abcd") 
    call reverseString("bcd") 
    call reverseString("cd") 
     call reverseString("d") 
     call reverseString("") 
      return "" 
     add "d" then return 
     add "c" then return 
    add "b" then return 
    add "a" then return