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.

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.

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 umgekehrter Reihenfolge ausgeführt wird.

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

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

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

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

<- Meistern Sie diese Idee!

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

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)

• 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.

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!