Was ist Rekursion? Detaillierte Erklärung der Rekursion in Javascript

Der Inhalt dieses Artikels befasst sich mit der Frage, was Rekursion ist. Die detaillierte Erklärung der Rekursion in JavaScript hat einen gewissen Referenzwert. Freunde in Not können darauf zurückgreifen.

1. Was ist Rekursion?

Das Konzept der Rekursion ist sehr einfach: „Nehmen Sie die Funktion als Beispiel unten“.

Bevor Sie die Rekursion analysieren, müssen Sie das Konzept des „Aufrufstapels“ in JavaScript verstehen.

2. Push and Pop

Was ist ein Stapel? Es kann verstanden werden, dass es sich um einen bestimmten Bereich im Speicher handelt. Dieser Bereich wird mit einer Kiste verglichen. Wenn Sie etwas in die Kiste legen, wird durch diese Aktion der Stapel verschoben. Das erste, was Sie also ablegen müssen, ist unten in der Schachtel, und das letzte, was Sie ablegen müssen, ist oben in der Schachtel. Etwas aus der Schachtel zu nehmen kann als *aus dem Stapel geschoben werden.

Wir kommen also zu dem Schluss, dass wir die Angewohnheit haben, die Dinge von oben nach unten zu nehmen, und das Letzte, was wir bekommen.

Wenn in JavaScript eine Funktion aufgerufen wird, tritt das Stapelverhalten (Pop) erst auf, wenn ein Satz gefunden wird, der das Schlüsselwort return enthält, oder die Ausführung endet.

Nehmen wir ein Beispiel. Wie ist die Ausführungsreihenfolge dieses Codes?

function fn1() {
    return 'this is fn1'
}

function fn2() {
    fn3()
    return 'this is fn2'
}

function fn3() {
    let arr = ['apple', 'banana', 'orange']
    return arr.length
}

function fn() {
    fn1()
    fn2()
    console.log('All fn are done')
}

fn()

Eine Reihe von Stack-Pushing- und Popping-Verhalten ist oben aufgetreten:

Zuerst ist der Stack (Box) zu Beginn leer

2 , fn wird zuerst auf den Stapel geschoben und am unteren Rand des Stapels (Box) platziert

3 Innerhalb der Funktion fn wird die Funktion fn1 zuerst ausgeführt und fn1 wird auf den Stapel oberhalb von fn geschoben

4. Funktion fn1 wird ausgeführt, und wenn Sie zum Schlüsselwort „return“ wechseln, wird fn1 vom Stapel entfernt, und jetzt ist nur noch fn

im Feld übrig Innerhalb von fn beginnt nach der Ausführung von fn1 die Funktion fn2 mit der Ausführung und wird fn2 auf den Stapel geschoben, aber nachdem innerhalb von fn2 fn3 angetroffen wird, beginnt die Ausführung von fn3, sodass fn3 auf den Stapel geschoben wird

6. Zu diesem Zeitpunkt ist die Reihenfolge von unten nach oben im Stapel: fn3

7 Analog dazu gilt, wenn ein Satz mit dem Wenn das Schlüsselwort „return“ in der Funktion „fn3“ gefunden wird, verlässt fn3 nach der Ausführung den Stapel und kehrt zur Funktion „fn2“ zurück. Auch fn2 trifft auf das Schlüsselwort „return“ und springt weiterhin aus dem Stapel.

8. Jetzt ist nur noch fn auf dem Stapel. Kehren Sie zur Funktion fn zurück und führen Sie die Anweisung console.log('Alle fn sind fertig') aus.

9. Jetzt ist der Stapel wieder leer.

Die oben genannten Schritte können leicht verwirren. Hier ist das Flussdiagramm:

Sehen Sie sich die Ausführung in der Chrome-Browserumgebung an:

3. Rekursion

Sehen wir uns zunächst einfaches JavaScript an Rekursion

function sumRange(num) {
  if (num === 1) return 1;
  return num + sumRange(num - 1)
}

sumRange(3) // 6

Die obige Code-Ausführungssequenz:

1. Die Funktion sumRange(3) wird auf den Stapel verschoben und das Schlüsselwort return wird angetroffen, kann aber nicht sofort aus dem Stapel entfernt werden, da der Aufruf SumRange(num - 1) sumRange(2)

2 ist. Daher wird sumRange(2) auf den Stapel geschoben und so weiter, sumRange(1) ist auf den Stapel geschoben,

3 Schließlich öffnet sumRange(1) den Stapel und gibt 1 zurück, sumRange(2) öffnet den Stapel und gibt 2 zurück, sumRange(3) öffnet den Stapel

4, also ist das Ergebnis von 3 + 2 + 1 6

Siehe den Prozess Abbildung

Also, Rekursion ist auch ein Prozess des Schiebens und Knallens des Stapels.

Rekursion kann als nicht rekursiv ausgedrückt werden. Das Folgende ist die äquivalente Ausführung des obigen rekursiven Beispiels

// for 循环
function multiple(num) {
    let total = 1;
    for (let i = num; i > 1; i--) {
        total *= i
    }
    return total
}
multiple(3)

4. Zu beachtende Rekursionspunkte >Wenn das obige Beispiel wie folgt geändert wird:

function multiple(num) {
    if (num === 1) console.log(1)
    return num * multiple(num - 1)
}

multiple(3) // Error: Maximum call stack size exceeded

In der ersten Zeile des obigen Codes gibt es keinen Rückgabeschlüsselwortsatz. Da es keine Beendigungsbedingung für die Rekursion gibt, wird sie immer weitergegeben den Stapel, was zu einem Speicherverlust führt.

Rekursionsanfällige Fehlerpunkte

Es ist kein Endpunkt festgelegt
Außer bei Rekursion, andere Teilecode
Wann ist Rekursion angemessen?
Okay, das Obige ist das Konzept der Rekursion in JavaScript.

Das Folgende sind Übungsfragen.

6. Übungsfragen

1. Schreiben Sie eine Funktion, die eine Zeichenfolge akzeptiert und eine Zeichenfolge zurückgibt, die die Umkehrung der ursprünglichen Zeichenfolge ist.

2. Schreiben Sie eine Funktion, die eine Zeichenfolge akzeptiert und ein Zeichen von vorne nach hinten vergleicht. Wenn die beiden gleich sind, geben Sie „true“ zurück.

3. Schreiben Sie eine Funktion, die ein Array akzeptiert und ein abgeflachtes neues Array zurückgibt.

4. Schreiben Sie eine Funktion, die ein Objekt akzeptiert. Wenn der Objektwert eine gerade Zahl ist, addieren Sie sie und geben Sie den Gesamtwert zurück.

5. Schreiben Sie eine Funktion, die ein Objekt akzeptiert und ein Array zurückgibt. Dieses Array enthält alle Werte im Objekt, die Zeichenfolgen sind

Referenzantwort

Referenz 1

function reverse(str) {
   if(str.length <p>Referenz 2</p><pre class="brush:php;toolbar:false">function isPalindrome(str){ 
    if(str.length === 1) return true;
    if(str.length === 2) return str[0] === str[1]; 
    if(str[0] === str.slice(-1)) return isPalindrome(str.slice(1,-1)) 
    return false; 
}
var str = 'abba'
isPalindrome(str)

Referenz 3

function flatten (oldArr) {
   var newArr = [] 
   for(var i = 0; i <p>Referenz 4</p><pre class="brush:php;toolbar:false">function nestedEvenSum(obj, sum=0) {
    for (var key in obj) { 
        if (typeof obj[key] === 'object'){ 
            sum += nestedEvenSum(obj[key]); 
        } else if (typeof obj[key] === 'number' && obj[key] % 2 === 0){ 
            sum += obj[key]; 
        }
     } 
     return sum;
}
nestedEvenSum({c: 4,d: {a: 2, b:3}})

Referenz 5

function collectStrings(obj) {
    let newArr = []
    for (let key in obj) {
        if (typeof obj[key] === 'string') {
            newArr.push(obj[key])
        } else if(typeof obj[key] === 'object' && !Array.isArray(obj[key])) {
           newArr = newArr.concat(collectStrings(obj[key]))
        }
    }
    return newArr
}
var obj = {
        a: '1',
        b: {
            c: 2,
            d: 'dd'
        }
    }
collectStrings(obj)

5. Zusammenfassung

Das Wesentliche bei der Rekursion ist, dass man oft zuerst über den regulären Teil nachdenken muss. Bei der Betrachtung des rekursiven Teils werden die folgenden Methoden häufig in der JavaScript-Rekursion verwendet:

Array: Slice, Concat

String: Slice, Substr, Substring

Objekt: Object.assign

Das obige ist der detaillierte Inhalt vonWas ist Rekursion? Detaillierte Erklärung der Rekursion in Javascript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!