Fonctions récursives, partie 2

Chaque fonction récursive comporte les deux mêmes parties :

1. Le cas de base indique quand s’arrêter.
2. L’étape récursive appelle la fonction avec une entrée plus petite.

La factorielle de n est n * (n - 1) * ... * 1, donc la factorielle de n est égale à n fois la factorielle de n - 1 :

func factorial(n: int) -> int:
	if n == 1: # cas de base
		return 1
	return n * factorial(n - 1) # étape récursive

factorial(5) appelle factorial(4), qui appelle factorial(3), jusqu’à factorial(1), qui renvoie 1. En remontant, chaque appel effectue une multiplication : le résultat est 120.

Une entrée plus petite ne signifie pas nécessairement un nombre plus petit. Une chaîne plus courte fonctionne aussi. Cette fonction inverse une chaîne :

func reverse_text(text: String) -> String:
	if text.length() <= 1: # cas de base
		return text
	return reverse_text(text.substr(1)) + text[0]

text.substr(1) est la chaîne sans son premier caractère. La fonction inverse cette chaîne plus courte et ajoute le premier caractère à la fin. Une chaîne de zéro ou un caractère est déjà inversée : c’est le cas de base.

print(reverse_text("hello"))

olleh