Detaillierte Analyse klassischer Fragen zu JavaScript-Rekursionsfällen

Was ist Rekursion und wie funktioniert sie?

Schauen wir uns zunächst die Definition der Rekursion an:

Rekursion ist eine effiziente Methode zur Lösung von Problemen, bei denen eine Funktion sich selbst als Unterprogramm aufruft.

Einfach ausgedrückt wird die Programmiertechnik, bei der ein Programm sich selbst aufruft, Rekursion genannt. Die Idee der Rekursion besteht darin, ein großes und komplexes Problem Schicht für Schicht in ein Problem umzuwandeln, dessen Maßstab kleiner ist als das ursprüngliche Problem. Nachdem das Problem in Unterprobleme zerlegt wurde, werden rekursive Aufrufe fortgesetzt, bis die Unterprobleme ohne weitere Rekursion gelöst werden können.

Bei der Verwendung von Rekursion müssen Sie Endlosschleifen vermeiden. Um sicherzustellen, dass die Rekursion korrekt funktioniert, sollten rekursive Programme zwei Eigenschaften enthalten:

1. Bottom Cases: Bottom Cases werden verwendet, um sicherzustellen, dass Programmaufrufe rechtzeitig zurückkehren und nicht weiter rekursiv sind, wodurch sichergestellt wird, dass das Programm beendet werden kann.
2. Eine Rekurrenzrelation, die alle anderen Fälle in Basisfälle zerlegt.

Eine Funktion, die sich selbst aufruft, ist rekursiv. Denken Sie daran, eine Beendigungsbedingung festzulegen, sonst tritt eine Endlosschleife ein.

1. Summe

(1) Digitale Summation

    Funktion Summe(n){
      wenn(n===1){
        Rückgabewert n=1
      }
      Rückgabewert n+Summe(n-1)
    }
    console.log(Summe(5));

Ausführungsreihenfolge

5+Summe(n-1)
5+4+Summe(n-1)
5+4+3+Summe(n-1)
5+4+3+2Summe(n-1)
5+4+3+2+1

(2) Array-Summierung

        Funktion Summe(arr) {
        var len = arr.Länge
        wenn (Länge == 0) {
          Rückgabe 0
        } sonst wenn (Länge == 1) {
          Rückgabewert [0]
        } anders {
          returniere arr[0] + Summe(arr.slice(1))
        }
      }
      sei arr = [ 1, 2, 3, 4, 5 ]  
      console.log(Summe(arr))

Ausführungsreihenfolge

1+Summe(2,3,4,5)
1+2+Summe(3,4,5)
1+2+3(4,5)
1+2+3+4+Summe(5)
1+2+3+4+5
1+2+3+9
1+2+12
1+14
15

2. Datenübertragungsbaum

        lass Daten = [{
                ID: "01",
                pid: "",
                "Name": "Lao Wang"
            },
            {
                ID: "02",
                pid: "01",
                "Name": "Xiao Zhang"
            }
        ]

  Funktion fn(data, rootId = '') {
            const children = [] //definiere ein leeres Array data.forEach(item => {
                if (item.pid === rootId) { //Wenn die pid=rootId jedes Elements zum Array children.push(item) hinzugefügt wird
                    Artikel.Kinder = fn(Daten, Artikel.ID)
                }
            });
            Kinder zurückgeben
        }

Verwenden Sie eine rekursive Baumtransformation, um den Wert der Root-PID als Ausgangspunkt zu ermitteln, bevor Sie mit dem nächsten Schritt fortfahren.

Ausführungsreihenfolge

3. Turm von Hanoi

Die folgenden drei Spalten sind als a, b und c festgelegt. Ziel ist es, alle Platten in a in der Reihenfolge von groß nach klein in die Spalte c zu legen. Es kann immer nur eine Platte gleichzeitig verschoben werden.

Umsetzungsideen:

1. Bewegen Sie n-1 Platten von a nach b
2. Verschiebe n Datenträger von A nach C
3. Bewegen Sie n-1 Platten von b nach c

        Funktion fn(Num, Start, Mitte, Ende) {   
            wenn(Zahl>0){
                fn(num-1,Start,Ende,Mitte)
                Konsole.log(Start+'====>'+Ende); 
                fn(num-1,Mitte,Start,Ende)
            }
           }
              fn(2,'a','b','c')

Dabei sei Num die Anzahl der Platten, wobei Platte A der Anfang, Platte B die Mitte und Platte C das Ende ist.

Zum Beispiel die Ausführungsreihenfolge von 2 Platten

1. Bringen Sie in die erste Zeile 2 und num>0 ein. Führen Sie die erste Funktion fn(2-1,start,end,middle) aus. Führen Sie dann fn(1-1,start,end,middle) aus. Stellen Sie fest, dass num nicht größer als 0 ist. Und nicht nur das: Schauen Sie sich fn(2-1,start,end,middle) noch einmal an und geben Sie console.log(a===>b) aus.

2. Die zweite Zeile console.log(start+'====>'+end); gibt direkt a===>c aus

3. Die dritte Zeile fn(2-1,middle,start,end) führt console.log(b===>c) aus und beim nächsten Mal kann fn(1-1,middle,start,end) nicht in die Schleife eintreten und die Ausführung wird abgeschlossen

Die Ausführungsreihenfolge ist etwas abstrakt. Wenn Sie sie wirklich nicht verstehen, folgen Sie einfach der einfachsten Denkweise. fn(num, start, middle, end) ist die Art, wie wir normalerweise Spiele spielen. Das anfängliche Diagramm

fn(num-1,start,middle,end) Nimm den zweiten Parameter „position“ als die zu bewegende Platte und den vierten Parameter „position“ als das zu bewegende Ziel. Bringe diese Formel jedes Mal ein, wenn du das Bild anschaust.

Schritt 1 fn(num-1,start,end,middle) Wenn es beispielsweise zwei Platten gibt, muss a-1 zuerst auf b platziert werden.

Der zweite Schritt besteht darin, Platte A auf C zu legen und direkt console.log('a===>c') auszugeben.

Der dritte Schritt besteht darin, Platte b auf c zu legen fn(num-1,middle,start,end,)

4. Fibonacci-Folge

Die Fibonacci-Folge, auch bekannt als Goldene Schnitt-Folge, wurde vom Mathematiker Leonardo da Fibonacci am Beispiel der Kaninchenreproduktion eingeführt und wird daher auch „Kaninchen-Folge“ genannt. Es handelt sich dabei um eine Zahlenfolge: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,

        Funktion Fibonacci(n) {
            gibt n <= 1?1:Fibonacci(n - 1) + Fibonacci(n - 2) zurück
        }

Mit Ausnahme der ersten beiden ist jedes Mal die Summe der vorherigen Zahl und der beiden vorherigen Zahlen gleich der dritten Zahl.

Beispielsweise die Zahl 5. Der erste Term ist 3. Die ersten beiden Terme sind 2. 3+2=5.

Zusammenfassen

Dies ist das Ende dieses Artikels über die detaillierte Analyse klassischer Fragen zum rekursiven Fall in JavaScript. Weitere relevante Inhalte zum rekursiven Fall in JavaScript finden Sie in früheren Artikeln auf 123WORDPRESS.COM oder in den folgenden verwandten Artikeln. Ich hoffe, dass jeder 123WORDPRESS.COM in Zukunft unterstützen wird!