Introduction
Récursion
Les fonctions récursives sont des fonctions qui s'appellent elles-mêmes.
Une fonction récursive doit avoir au moins un cas de base et au moins un cas récursif.
Un cas de base renvoie une valeur sans rappeler la fonction.
Un cas récursif rappelle la fonction, en modifiant l'entrée pour qu'elle finisse par correspondre au cas de base.
Voici un exemple qui compte les éléments d'un tableau.
def count:
if length == 0 then
0 # base case
else
1 + (.[1:] | count) # recursive case
end;
([] | count), # => 0
([11, 22, 33] | count) # => 3
Une fonction récursive peut avoir plusieurs cas de base et/ou plusieurs cas récursifs.
Par exemple, la suite de Fibonacci est une suite récursive avec deux cas de base.
def fibonacci:
if . == 0 then
0
elif . == 1 then
1
else
(. - 1 | fibonacci) + (. - 2 | fibonacci)
end;
10 | fibonacci # => 55
Compter le nombre d'occurrences d'une valeur donnée x dans un tableau a deux cas récursifs.
def count_occurrences(x):
if length == 0 then
0
elif first == x then
1 + (.[1:] | count_occurrences(x))
else
(.[1:] | count_occurrences(x))
end;
[11, 22, 33, 22, 44] | count_occurrences(22) # => 2
En pratique, pour parcourir des tableaux et d'autres structures de données énumérables, on utilise le plus souvent des fonctions intégrées, comme map et reduce, ou bien on utilise des flux comme [.[] | select(...)].
Sous le capot, certaines fonctions intégrées sont implémentées à l'aide de la récursion.
Instructions
Tu viens de rejoindre une équipe qui maintient un pipeline de données basé sur jq.
Lors de ta première session en binôme, ton nouveau collègue se montre curieux :
« Tu sais comment add, reverse et map fonctionnent sous le capot ? Allons voir ça : essaie de les réimplémenter toi-même avec la récursivité, sans les fonctions intégrées. »
1. Implémente une fonction qui additionne les nombres d'un tableau
On va réimplémenter le filtre add intégré pour nous entraîner à la récursivité.
Le cas de base est qu'un tableau vide a une somme de zéro.
Implémente-le toi-même avec une fonction récursive ; n'utilise pas le filtre add intégré.
[5, 4, 6, 10] | array_add # => 25
2. Inverse un tableau
On va réimplémenter le filtre reverse intégré.
Le cas de base est que l'inverse d'un tableau vide est un tableau vide.
Implémente-le toi-même avec une fonction récursive ; n'utilise pas le filtre reverse intégré.
[5, 4, 6, 10] | array_reverse # => [10, 6, 4, 5]
On va réimplémenter le filtre map intégré.
Cette fonction prend un filtre en paramètre, applique ce filtre à chaque élément du tableau d'entrée, puis renvoie les résultats dans un nouveau tableau.
Le cas de base est qu'un tableau vide donne un tableau vide.
Implémente-le toi-même avec une fonction récursive ; n'utilise pas le filtre map intégré.
[5, 4, 6, 10] | array_map(. + 10) # => [15, 14, 16, 20]
Exercice d'apprentissage
