Rekursive string-Umkehr-Funktion in javascript?

Ich bin ein ziemlich erfahrener frontend-engineer mit einer schwachen CS-hintergrund. Ich versuche, meinen Kopf um das Konzept der Rekursion. Die meisten Beispiele und angeblichen Erklärungen, die ich finden kann sind einfach nicht zu erklären, es in einer Weise, die ich finden einfach zu verstehen.

Ich setze mir eine Aufgabe schreiben Sie eine Funktion reverse, die eine Zeichenkette rekursiv. Ich weiß, es hat ein Basis-Zustand (d.h. die Lösung ist gefunden), aber ich kann nicht herausfinden, wie man eigentlich so etwas schreiben und konnte die demo nutzen, um zu studieren.

Könnte mir jemand eine Probe geben Funktion?

InformationsquelleAutor Geuis | 2011-02-01

javascript recursion

28

Etwas wie:
```
function reverse (str) {
    if (str === "") {
        return "";
    } else {
        return reverse(str.substr(1)) + str.charAt(0);
    }
}
```
Also die Funktion ist rekursiv, wie Sie es selbst nennt, um die Arbeit zu tun.
- So einfach, wie es erhält.
- Danke. Das ist für mich wirklich leicht zu verstehen. Ich werde weiter versuchen, um zu sehen, wenn ich manuell umkehren eines Arrays rekursiv.
- Die array-version, werden sehr viel schwieriger, da arrays in ECMAScript (von denen JavaScript ist eine Implementierung) sind rein Imperativ...
- Dies ist, was ich Tat, für die Rückwärtsfahrt ein array: var x = function(arr){ if( arr.Länge === 1 ){ return arr; }else{ return x( arr.slice(1) ).concat(arr[0]); } } console.log( x([1,2,3,4]) );
- Schöne demonstration. FYI, das umkehren einer Zeichenfolge, die Sie nicht brauchen Rekursion: [classextender].teilen ("split").reverse().join(") würde das gleiche tun 😉
- Ja, ich weiß. Das war einfach so, ich kann meinen Kopf um die Rekursion.
- slice() vorzuziehen ist, um substr(): es ist standardisiert in der ECMAScript-Spezifikation und arbeitet einheitlich cross-browser.
- Ich habe eine Korrektur dieser. In einem Fall, den Sie beschrieben haben, dauert es +1 die Rekursion iteration zu beenden, einen job. Wenn Sie "if" - Anweisung: "if(str.Länge === 1) { return str; }", die es dauern wird, genaue Anzahl der Operationen als die Länge der Zeichenfolge ist ohne zusätzliche ausführen, um wieder eine leere Zeichenkette das Ergebnis. Aber in diesem Fall jedes mal, wenn str.Länge aufgerufen werden. Ich muss die benchmark das 🙂
- Hier ist mein benchmark zeigt die Leistung Unterschied: jsperf.com/recursive-string-revert. Auch verwenden .substr() über .slice() ist ein wenig schneller, zumindest in Chrome.
InformationsquelleAutor Tom
3

Einen tail-rekursive version, nur zum Spaß (auch wenn JavaScript nicht funktioniert tail call elimination):
```
function reverse(str) {
  function r(s, acc) {
    return (s.length == 0) ? acc : r(s.substr(1), s.charAt(0) + acc);
  };
  return r(str, '');
};
```
- was meinst du mit auch wenn JavaScript nicht optimieren?
- Viele compilers/interpreters ausführen tail call elimination (einige language-specs sogar erfordern), die macht der tail-rekursiven Funktionen führen vergleichsweise zu Ihre iterativen Gegenstücke. Die ECMAScript-Spezifikation hat keine solche Anforderung und keine bestehenden JavaScript-Interpreter es tun, soweit ich weiß.
- in ES6-Spezifikation, Schwanz Anrufe werden jetzt richtig interpretiert.
InformationsquelleAutor maerics

25% schnellere Funktion: jsperf.com

JS:

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

InformationsquelleAutor Dima Daron

0

Einer Zeile code mit ternäre Operatoren Sie können ganz einfach umkehren.

Erklärung: wenn string vorhanden ist (wenn nicht null) dann return Rekursion sonst stoppen die Rekursion.
```
  function reverseString(str) {
    return (str ? reverseString(str.substring(1)) + str.charAt(0) : str);
  }
```
Funktionsaufruf:
```
console.log(reverseString('hello'));
```
InformationsquelleAutor Eugene Sunic

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

InformationsquelleAutor Rahul kishan

//Aufruf dieser Funktion mit dem string als parameter

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

InformationsquelleAutor shantanu kaushik

0

Entsprechend der MDN Web-Docs, sollten Sie substring() statt substr():

Warnung: Obwohl String.prototype.substr(…) ist nicht unbedingt veraltet (wie in "aus dem Web entfernt Normen"), wird es als ein legacy Funktion und sollte vermieden werden wenn möglich. Es ist nicht Teil der core-Sprache "JavaScript" aus und kann entfernt werden, in der Zukunft. Wenn möglich, verwenden Sie die substring() Methode statt.

Zusätzlich, wenn kein index zur Verfügung gestellt, die als parameter charAt(), der Standardwert ist 0.

Daher können wir schreiben einen rekursiven one-liner, um das umkehren einer Zeichenfolge mit einem ternärer operator und durch die Anwendung der Logik oben beschrieben:

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

console.log(reverse_string('Hello, world!')); //!dlrow ,olleH
```
InformationsquelleAutor Grant Miller

-1

Bisher das beste, was ich denke:

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

InformationsquelleAutor qweszxcj

-1

Versuchen Sie dies:

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))  
  }
}

InformationsquelleAutor Gerrat

-3

Dies ist eine ziemlich einfache C# - Implementierung des Algorithmus, den Sie gefragt haben.
Ich denke, es könnte umgeschrieben werden in javascript ziemlich einfach.

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

InformationsquelleAutor Development 4.0

-3

Es ist ausführlich, aber ich wie machen es leicht zu verstehen, in logische Schritte:

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

}

Dann nennen mag:

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

InformationsquelleAutor Jonathan Borthwick

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.