La récursivité n'est pas difficile: une présentation étape par étape de cette technique de programmation utile

Je vais le dire dès le départ. Connaissez-vous les événements qui se produisent lors de l'invocation de fonction? Non? Alors c'est là que nous allons commencer.

Appel de fonction

Lorsque nous appelons une fonction, un contexte d'exécution est placé sur la pile d'exécution. Décomposons cela un peu plus.

Tout d'abord, qu'est-ce qu'une pile?

Une pile est une structure de données qui fonctionne sur la base du «dernier entré, premier sorti». Un élément est "poussé" sur une pile pour y être ajouté, et un élément est "sorti" de la pile pour le retirer.

L'utilisation d'une pile est une méthode pour ordonner certaines opérations à exécuter.

Maintenant, revenons à ce qu'est un contexte d'exécution? Un contexte d'exécution se forme lors d'un appel de fonction. Ce contexte se place sur une pile d'exécution, un ordre d'opérations. L'élément qui est toujours le premier dans cette pile est le contexte d'exécution global. Viennent ensuite tous les contextes créés par une fonction.

Ces contextes d'exécution ont des propriétés, un objet d'activation et une liaison «this». La liaison «this» est une référence à ce contexte d'exécution. L'objet d'activation comprend: les paramètres passés, les variables déclarées et les déclarations de fonction.

Ainsi, chaque fois que nous plaçons un nouveau contexte sur la pile, nous avons généralement tout ce dont nous avons besoin pour exécuter du code.

Pourquoi est-ce que je dis habituellement ?

Avec la récursivité, nous attendons des valeurs de retour provenant d'autres contextes d'exécution. Ces autres contextes sont plus haut dans la pile. Lorsque le dernier élément de la pile termine l'exécution, ce contexte génère une valeur de retour. Cette valeur de retour est transmise en tant que valeur de retour du cas récursif à l'élément suivant. Ce contexte d'exécution est ensuite sorti de la pile.

Récursion

Alors, qu'est-ce que la récursivité?

Une fonction récursive est une fonction qui s'appelle elle-même jusqu'à ce qu'une «condition de base» soit vraie et que l'exécution s'arrête.

Bien que false, nous continuerons à placer les contextes d'exécution au-dessus de la pile. Cela peut arriver jusqu'à ce que nous ayons un «débordement de pile». Un débordement de pile se produit lorsque nous manquons de mémoire pour contenir des éléments dans la pile.

En général, une fonction récursive comprend au moins deux parties: une condition de base et au moins un cas récursif.

Regardons un exemple classique.

Factorielle

const factorial = function(num) { debugger; if (num === 0 || num === 1) { return 1 } else { return num * factorial(num - 1) }}
factorial(5)

Ici, nous essayons d'en trouver 5! (cinq factorielles). La fonction factorielle est définie comme le produit de tous les entiers positifs inférieurs ou égaux à son argument.

La première condition stipule: «si le paramètre passé vaut 0 ou 1, nous quitterons et retournerons 1».

Ensuite, le cas récursif indique:

«Si le paramètre n'est pas 0 ou 1, alors nous passerons valeur de numfois la valeur de retour de l'appel à nouveau de cette fonction avec num-1comme argument».

Donc, si nous appelons factorial(0), la fonction renvoie 1 et n'atteint jamais le cas récursif.

La même chose vaut pour factorial(1).

Nous pouvons voir ce qui se passe si nous insérons une instruction de débogage dans le code et utilisons les outils de développement pour y faire un pas et regarder la pile d'appels.

  1. La pile d'exécution place factorial()5 comme argument passé. Le cas de base est faux, entrez donc la condition récursive.
  2. La pile d'exécution place factorial()une seconde fois avec num-1= 4 comme argument. Le cas de base est faux, entrez une condition récursive.
  3. La pile d'exécution place factorial()une troisième fois avec num-1(4–1) = 3 comme argument. Le cas de base est faux, entrez une condition récursive.
  4. La pile d'exécution place factorial()une quatrième fois avec num-1(3–1) = 2 comme argument. Le cas de base est faux, entrez une condition récursive.
  5. La pile d'exécution place factorial()une cinquième fois avec num-1(2–1) = 1 comme argument. Maintenant, le cas de base est vrai, alors renvoyez 1.

À ce stade, nous avons diminué l'argument de un à chaque appel de fonction jusqu'à ce que nous atteignions une condition pour retourner 1.

6. À partir de là, le dernier contexte d'exécution se termine,, de num === 1sorte que la fonction renvoie 1.

7. Ensuite num === 2, la valeur de retour est 2. (1 × 2).

8. Ensuite num === 3, la valeur de retour est 6, (2 × 3).

Jusqu'à présent, nous avons 1 × 2 × 3.

9. Ensuite, num === 4(4 × 6). 24 est la valeur de retour au contexte suivant.

10. Enfin, num === 5(5 × 24) et nous avons 120 comme valeur finale.

La récursivité est assez soignée, non?

Nous aurions pu faire la même chose avec une boucle for ou while. Mais l'utilisation de la récursivité donne une solution élégante et plus lisible.

C'est pourquoi nous utilisons des solutions récursives.

Plusieurs fois, un problème décomposé en parties plus petites est plus efficace. Diviser un problème en parties plus petites aide à le surmonter. Par conséquent, la récursivité est une approche de division pour résoudre des problèmes.

  • Sub-problems are easier to solve than the original problem
  • Solutions to sub-problems are combined to solve the original problem

“Divide-and-conquer” is most often used to traverse or search data structures such as binary search trees, graphs, and heaps. It also works for many sorting algorithms, like quicksort and heapsort.

Let’s work through the following examples. Use devtools to get a conceptual grasp of what’s happening where and when. Remember to use debugger statements and step though each process.

Fibonacci

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

Recursive arrays

function flatten(arr) { var result = [] arr.forEach(function(element) { if (!Array.isArray(element)) { result.push(element) } else { result = result.concat(flatten(element)) } }) return result}
flatten([1, [2], [3, [[4]]]]);

Reversing a string

function reverse(str) { if (str.length === 0) return '' return str[str.length - 1] + reverse(str.substr(0, str.length - 1))}
reverse('abcdefg');

Quicksort

function quickSort(arr, lo, hi) { if (lo === undefined) lo = 0 if (hi === undefined) hi = arr.length - 1
 if (lo  partition: ' + p) // sort subarrays quickSort(arr, lo, p - 1) quickSort(arr, p + 1, hi) } // for initial call, return a sorted array if (hi - lo === arr.length - 1) return arr}
function partition(arr, lo, hi) { // choose last element as pivot var pivot = arr[hi] // keep track of index to put pivot at var pivotLocation = lo // loop through subarray and if element <= pivot, place element before pivot for (var i = lo; i < hi; i++) { if (arr[i] <= pivot) { swap(arr, pivotLocation, i) pivotLocation++ } } swap(arr, pivotLocation, hi) return pivotLocation}
function swap(arr, index1, index2) { if (index1 === index2) return var temp = arr[index1] arr[index1] = arr[index2] arr[index2] = temp console.log('swapped' + arr[index1], arr[index2], +' in ', arr) return arr}
quickSort([1, 4, 3, 56, 9, 8, 7, 5])

Practicing recursive techniques is important. For nested data structures like trees, graphs, and heaps, recursion is invaluable.

In a future article, I will discuss tail-call optimization and memoization techniques as they relate to recursion. Thanks for reading!

Further resources

Wikipedia

Software Engineering

Another good article

M.I.T. open courseware