Note: Si vous copier plusieurs fois le code dans une console web, vous pouvez avoir une erreur car une variable déclarée avec let avec le même nom a déjà été déclaré précédemment. Le plus simple est d'ouvrir une console web dans un autre onglet, ou d'enlever le let pour tester le code.

Idée générale

Voici plusieurs formulations de l'idée générale, illustréés par des exemples d'illustration juste après:

• Une fonction récursive réutilise le résultat renvoyé (via return) et s'arrête quand on arrive au premier élément.

• Une fonction récursive s'appelle elle-même sur le même problème de plus en plus petit et s'arrête quand elle a trouvé un problème pour lequel elle a une solution

Définir une fonction itérative

Pour définir une fonction itérative, on procède en deux étapes.

Etape 1: Définir la première valeur de la fonction: le cas de base

On doit définir quand la fonction récursive s'arrête, c'est à dire la "plus petite" solution au problème.

Etape 2: Définir comment se répércute la fonction récursive: le cas de propagation

On doit définir comment la fonction se décompose, et fait appel à la même fonction sur un cas plus petit. La fonction récurive se propagera jusqu'à faire appel au cas de base.

Programmer une fonction récursive

Principe général

La différence entre une fonction "habituelle" et une fonction récursive est dans la définition de la fonction. Dans une fonction récursive, on appelle la fonction dans sa définition (nom et arguments). Si vous vous rappelez, on rappelle la même fonction sur un "problème plus petit" comme défini dans le cas de propagation. On s'arrête quand on est dans le cas de base.

Etape 1 programmer le cas de base; Etape 2 programmer le cas de propagation

En lien avec le fait de s'arrêter quand on est dans le cas de base, dans une fonction récursive, on vérifie en premier lieu si on est dans le cas de base: dans ce cas on s'arrête et on retourne le résultat du cas de base.

Si on ne se trouve pas dans un cas de base, on retourne la formule de propagation. La formule de propagation contient forcément la fonction avec en attribut un problème plus petit.

Activité 1

Dans la suite, vous allez programmer étape par étape le premier exemple d'illustration en JavaScript (somme)

Mise en pratique 1

Vous allez ré-utiliser les exercices pour la fonction somme pour progammer des fonctions similaires

Activité 2

Dans la suite, vous allez programmer étape par étape le deuxième exemple d'illustration en JavaScript (palindrome)

Clôture

Vous avez suivi le cours et les activités sur les fonctions récursives. Vous avez vu que:

• les fonctions récursives s'appellent elle-mêmes sur un cas "plus simple"

• les fonctions récursives présentent :

  • au moins un cas de base (celui pour lequel on connait directement le résultat) et

  • au moins un cas de propagation (le cas qui fait appel à la fonction elle-même jusqu'à arriver à un cas de base)

• Quand on programme une fonction récursive, on programme ces cas de base et de propagation dans une condition.

• Quand on programme, le cas de base renvoie le résultat et le cas de propragation fait appel à la même fonction dans la déclaration de la fonction. Utilise return dans les deux cas.