Fonctions récursives, partie 1

Une fonction récursive est une fonction qui s’appelle elle-même. Chaque appel résout une version plus petite du problème, jusqu’à ce que le problème soit assez simple pour recevoir une réponse directe.

Cette fonction additionne les nombres entiers de 1 à n :

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

Il comporte deux parties :

• Le cas de base répond sans rappeler la fonction : la somme jusqu’à 0 est 0.
• L’étape récursive appelle la fonction avec une valeur plus petite, n - 1, et construit sa réponse à partir du résultat.

sum_to_n(3) vaut 3 + sum_to_n(2), qui vaut 3 + 2 + sum_to_n(1), qui vaut 3 + 2 + 1 + sum_to_n(0). Le cas de base renvoie 0, et les appels en attente se terminent un à un : le résultat est 6.

Chaque étape récursive doit se rapprocher du cas de base. Sans cas de base, ou avec une étape comme n + 1 qui ne l’atteint jamais, la fonction continue de s’appeler elle-même. Godot autorise environ 1 000 appels imbriqués, puis arrête le programme en signalant une erreur.