Kit d'entretien : récursion.

S'appeler encore et encore, mais devenir plus simple à chaque appel : c'est en un mot la récursion ! C’est une définition informelle, mais elle capture parfaitement l’essence.

Bien que la suite naturelle de mon dernier article sur la fenêtre coulissante soit le modèle à deux points, nous faisons un petit détour. Pourquoi? Parfois, aborder des concepts un peu différents peut effectivement faciliter l’apprentissage :

1) Cela donne au cerveau une certaine variété avec laquelle travailler.
2) Soyons réalistes, il n'y a qu'une quantité limitée de manipulations de tableaux que nous pouvons effectuer avant que les choses ne commencent à se brouiller !

De plus, la récursivité est une nécessité incontournable avant de plonger dans les arbres binaires, c'est pourquoi cet article se concentrera sur cela. Ne vous inquiétez pas, les présentations de modèles à deux points et d'arbres seront bientôt disponibles. Nous faisons juste un arrêt stratégique pour garder les choses au frais !

Récursion 101

La récursion est l'un de ces concepts où la construction de l'intuition compte plus que la mémorisation des définitions. L'idée clé ? Répétition et rendre le problème progressivement plus simple.

Alors, qu’est-ce que la récursion ?

La récursion consiste à répéter un processus encore et encore sur un problème, mais à chaque répétition, le problème devient plus simple jusqu'à ce que vous atteigniez un point où il ne peut plus être simplifié. C'est ce qu'on appelle le cas de base.

Décomposons-le avec quelques règles de base.

Règle 1 : le problème doit diminuer

À chaque itération, le problème devrait diminuer en taille ou en complexité. Imaginez commencer par un carré et, à chaque étape, vous le réduisez.

Remarque : si, au lieu d'un carré plus petit, vous obtenez des formes aléatoires, ce n'est plus un processus récursif, le problème le plus simple est la version plus petite du plus grand.

Règle 2 : il doit y avoir un cas de base

Un cas de base est la version la plus simple et la plus triviale du problème : le point où aucune autre récursion n'est nécessaire. Sans cela, la fonction continuerait à s'appeler indéfiniment, provoquant un débordement de pile.

Exemple : compte à rebours

Disons que vous avez un problème simple : compter à rebours de x à 0. Ce n'est pas un problème du monde réel, mais c'est une bonne illustration de la récursion.

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

Dans cet exemple, appeler count(10) déclenchera une série d'appels récursifs, chacun simplifiant le problème en soustrayant 1 jusqu'à ce qu'il atteigne le cas de base de 0. Une fois le cas de base atteint, la fonction cesse de s'appeler et la récursivité « bouillonne », ce qui signifie que chaque appel précédent termine son exécution dans l'ordre inverse.

Exemple d'arbre récursif

Voici une représentation ASCII du fonctionnement des appels récursifs avec count(3) :

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

Tout ce qui retourné de count(0) "bouillonnera" jusqu'à count(1)... jusqu'à count 3.

Cela se compose donc du cas de base le plus trivial !.

Plus de problèmes !

Exemples récursifs

Vous vous souvenez de la partie intuition ? plus vous résolvez de problèmes récursifs, mieux c'est, voici un bref aperçu des problèmes de récursivité classiques.

Factorielle

La factorielle d'un nombre n est le produit de tous les entiers positifs inférieurs ou égaux à n.

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

visuel

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

Remarquez comment la réponse calculée précédente bouillonne, la réponse de 2 * factorialRecursive(1) bouillonne pour être un argument pour 3 * factorialRecursive(2) et ainsi de suite... <- maîtrisez cette idée !

fibonnacci

Une fonction récursive qui renvoie le nième nombre de la séquence de Fibonacci, où chaque nombre est la somme des deux précédents, en commençant par 0 et 1.

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

Visuel

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)

Voici comment ça marche :

• fibonacci(4) appelle fibonacci(3) et fibonacci(2).
• fibonacci(3) se décompose en :
  • fibonacci(2) → Ceci se divise en fibonacci(1) (renvoie 1) et fibonacci(0) (renvoie 0). Leur somme est 1 + 0 = 1.
  • fibonacci(1) → Cela renvoie 1.
  • Donc, fibonacci(3) renvoie 1 (de fibonacci(2)) + 1 (de fibonacci(1)) = 2.
• fibonacci(2) tombe en panne à nouveau :
  • fibonacci(1) renvoie 1.
  • fibonacci(0) renvoie 0.
  • Leur somme est 1 + 0 = 1.
• Enfin, fibonacci(4) renvoie 2 (de fibonacci(3)) + 1 (de fibonacci(2)) = 3.

Défi d'optimisation : si vous remarquez dans la visualisation, fib(2) est calculé deux fois, c'est la même réponse, pouvons-nous faire quelque chose ? cache ? imaginez un gros problème de doublons !

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>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!

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!