Interview-Kit: Rekursion.

Sich selbst immer wieder anrufen, aber mit jedem Anruf einfacher werden – das ist Rekursion auf den Punkt gebracht! Es ist eine informelle Definition, aber sie fängt das Wesentliche perfekt ein.

Während die natürliche Fortsetzung meines letzten Artikels über Schiebefenster das Zwei-Zeiger-Muster wäre, machen wir einen kleinen Umweg. Warum? Manchmal kann es das Lernen tatsächlich einfacher machen, sich mit etwas anderen Konzepten auseinanderzusetzen:

1) Es gibt dem Gehirn etwas Abwechslung, mit der es arbeiten kann.
2) Seien wir ehrlich, wir können nur eine begrenzte Menge an Array-Manipulationen ertragen, bevor die Dinge anfangen, ineinander zu verschwimmen!

Außerdem ist Rekursion ein Muss, bevor man sich mit Binärbäumen beschäftigt, daher konzentriert sich dieser Artikel darauf. Keine Sorge – die Einführung von Zwei-Zeiger-Mustern und -Bäumen folgt bald. Wir machen nur einen strategischen Stopp, um die Dinge frisch zu halten!

Rekursion 101

Rekursion ist eines dieser Konzepte, bei denen der Aufbau von Intuition wichtiger ist als das Auswendiglernen von Definitionen. Die Schlüsselidee? Wiederholung und zunehmende Einfachung des Problems.

Was ist also Rekursion?

Bei der Rekursion geht es darum, einen Prozess für ein Problem immer wieder zu wiederholen, aber mit jeder Wiederholung wird das Problem einfacher, bis Sie einen Punkt erreichen, an dem es nicht mehr vereinfacht werden kann – dies wird als Basisfall.

Lassen Sie es uns anhand einiger Grundregeln aufschlüsseln.

Regel 1: Das Problem muss kleiner werden

Bei jeder Iteration sollte das Problem an Größe oder Komplexität abnehmen. Stellen Sie sich vor, Sie beginnen mit einem Quadrat und verkleinern es mit jedem Schritt.

Hinweis: Wenn Sie anstelle eines kleineren Quadrats zufällige Formen erhalten, handelt es sich nicht mehr um einen rekursiven Prozess. Das einfachere Problem ist die kleinere Version des größeren.

Regel 2: Es muss ein Basisfall vorliegen

Ein

Basisfall ist die einfachste und trivialste Version des Problems – der Punkt, an dem keine weitere Rekursion erforderlich ist. Ohne dies würde sich die Funktion ewig selbst aufrufen und einen Stapelüberlauf verursachen.

Beispiel: Countdown

Nehmen wir an, Sie haben ein einfaches Problem: von x bis 0 herunterzuzählen. Dies ist kein reales Problem, aber es ist ein gutes Beispiel für die Rekursion.

function count(x) {
  // Base case
  if (x == 0) {
    return 0;
  }

  // Recursive call: we simplify the problem by reducing x by 1
  count(x - 1);
  // will only run during the bubbling up
 // the first function call to run is the one before base case backwards
// The printing will start from 1....
  console.log(x)
}

In diesem Beispiel löst der Aufruf von count(10) eine Reihe rekursiver Aufrufe aus, von denen jeder das Problem vereinfacht, indem er 1 subtrahiert, bis der Basisfall 0 erreicht ist. Sobald der Basisfall erreicht ist, ruft die Funktion sich selbst nicht mehr auf und die Rekursion „blubbert“, was bedeutet, dass jeder vorherige Aufruf

in umgekehrter Reihenfolge ausgeführt wird.

Beispiel für einen rekursiven Baum

Hier ist eine ASCII-Darstellung, wie rekursive Aufrufe mit count(3) funktionieren:

count(3)
   |
   +-- count(2)
        |
        +-- count(1)
             |
             +-- count(0)
                 (base case: stop here)

Alles, was von count(0)

zurückgegeben wird, „blubbert“ bis count(1) ... bis count 3.

Es setzt sich also aus dem trivialsten Basisfall zusammen!.

Noch mehr Probleme!

Rekursive Beispiele

Erinnern Sie sich an den Intuitionsteil? Je mehr rekursive Probleme Sie lösen, desto besser. Dies ist ein kurzer Überblick über klassische Rekursionsprobleme.

Fakultät

Die Fakultät einer Zahl n ist das Produkt aller positiven ganzen Zahlen kleiner oder gleich n.

const factorialRecursive = num => {
    if(num === 0) {
        return 1;
    }
    return num * factorialRecursive(num - 1);
}

visuell

factorialRecursive(5)

factorialRecursive(5)
│
├── 5 * factorialRecursive(4)
│     │
│     ├── 4 * factorialRecursive(3)
│     │     │
│     │     ├── 3 * factorialRecursive(2)
│     │     │     │
│     │     │     ├── 2 * factorialRecursive(1)
│     │     │     │     │
│     │     │     │     ├── 1 * factorialRecursive(0)
│     │     │     │     │     │
│     │     │     │     │     └── returns 1
│     │     │     │     └── returns 1 * 1 = 1
│     │     │     └── returns 2 * 1 = 2
│     │     └── returns 3 * 2 = 6
│     └── returns 4 * 6 = 24
└── returns 5 * 24 = 120

Beachten Sie, wie die zuvor berechnete Antwort nach oben sprudelt, die Antwort von 2 * factialRecursive(1) nach oben sprudelt und ein Argument für 3 * factialRecursive(2) ist und so weiter ...

<- Meistern Sie diese Idee!

fibonnaci

Eine rekursive Funktion, die die n-te Zahl in der Fibonacci-Folge zurückgibt, wobei jede Zahl die Summe der beiden vorhergehenden ist, beginnend bei 0 und 1.

const fibonacci = num => {
    if (num <= 1) {
        return num;
    }
    return fibonacci(num - 1) + fibonacci(num - 2);
}

Visuell

Fibonacci(4)

fibonacci(4)
│
├── fibonacci(3)
│     ├── fibonacci(2)
│     │     ├── fibonacci(1) (returns 1)
│     │     └── fibonacci(0) (returns 0)
│     └── returns 1 + 0 = 1
│
├── fibonacci(2)
│     ├── fibonacci(1) (returns 1)
│     └── fibonacci(0) (returns 0)
└── returns 1 + 1 = 2


a bit tricky to visualize in ascii (way better in a tree like structure)

So funktioniert es:

• fibonacci(4) ruft fibonacci(3) und fibonacci(2) auf.
• Fibonacci(3) zerfällt in:
  • fibonacci(2) → Dies teilt sich in fibonacci(1) (gibt 1 zurück) und fibonacci(0) (gibt 0 zurück). Ihre Summe ist 1 + 0 = 1.
  • fibonacci(1) → Dies gibt 1 zurück.
  Also gibt
  • fibonacci(3) 1 (von fibonacci(2)) + 1 (von fibonacci(1)) = 2 zurück.
• Fibonacci(2) bricht wieder zusammen:
  • fibonacci(1) gibt 1 zurück.
  • fibonacci(0) gibt 0 zurück.
  Ihre Summe ist 1 + 0 = 1.
Schließlich gibt
• fibonacci(4) 2 (von fibonacci(3)) + 1 (von fibonacci(2)) = 3 zurück.

Optimierungsherausforderung: Wenn Sie in der Visualisierung bemerken, dass fib(2) zweimal berechnet wird, ist das die gleiche Antwort, können wir dann etwas tun? Cache? Stellen Sie sich ein großes Problem mit Duplikaten vor!

Sum Array

Write a recursive function to find the sum of all elements in an array.

  const sumArray = arr => {
    if(arr.length == 0){
        return 0
    }

    return arr.pop() + sumArray(arr)
}






</p>
<p>visual</p>

<p>sumArray([1, 2, 3, 4])<br>
</p>

<pre class="brush:php;toolbar:false">sumArray([1, 2, 3, 4])
│
├── 4 + sumArray([1, 2, 3])
│     │
│     ├── 3 + sumArray([1, 2])
│     │     │
│     │     ├── 2 + sumArray([1])
│     │     │     │
│     │     │     ├── 1 + sumArray([])
│     │     │     │     │
│     │     │     │     └── returns 0
│     │     │     └── returns 1 + 0 = 1
│     │     └── returns 2 + 1 = 3
│     └── returns 3 + 3 = 6
└── returns 4 + 6 = 10

This covers the basics, the more problems you solve the better when it comes to recursion.

I am going to leave a few challenges below:

Challenges for Practice

1. Check Palindrome: Write a recursive function to check if a given string is a palindrome (reads the same backward as forward).

console.log(isPalindrome("racecar")); // Expected output: true
console.log(isPalindrome("hello"));   // Expected output: false

1. Reverse String: Write a recursive function to reverse a given string.

console.log(reverseString("hello")); // Expected output: "olleh"
console.log(reverseString("world")); // Expected output: "dlrow"

1. Check Sorted Array: Write a recursive function to check if a given array of numbers is sorted in ascending order.

console.log(isSorted([1, 2, 3, 4]));    // Expected output: true
console.log(isSorted([1, 3, 2, 4]));    // Expected output: false

---

Recursion is all about practice and building that muscle memory. The more you solve, the more intuitive it becomes. Keep challenging yourself with new problems!

If you want more exclusive content, you can follow me on Twitter or Ko-fi I'll be posting some extra stuff there!

Das obige ist der detaillierte Inhalt vonInterview-Kit: Rekursion.. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!