Programmation Scheme/Récursivité
La récursivité, c'est lorsqu'une procédure s'appelle elle-même. Il faut impérativement prévoir une condition de fin, sans quoi l'appel récursif ne se termine jamais.
Un exemple simple : la factorielle
[modifier | modifier le wikicode]Calculons la factorielle d'un entier :
(define (factorielle n) (if (= n 0) 1 (* n (factorielle (- n 1)))))
Si l'on fait
(factorielle 0) ⇒ 1
en effet, puisque n vaut 0, l'évaluation de (= n 0) est #t, et donc l'évaluation de (if (= n 0) 1 (* n (factorielle (- n 1)))) est « 1 » (première expression suivant le booléen de if).
Si l'on fait
(factorielle 1) ⇒ 1
en effet, (= n 0) est #f, c'est la seconde expression suivant le booléen qui est évaluée, soit (* n (factorielle (- n 1))) →
(* 1 (factorielle 0)) (en remplaçant n par sa valeur, « 1 »).
Si l'on fait
(factorielle 4) ⇒ 24
car au final, on se retrouve à évaluer
(* 4 (factorielle 3))- →
(* 4 (* 3 (factorielle 2))) - →
(* 4 (* 3 (* 2 (factorielle 1)))) - →
(* 4 (* 3 (* 2 (* 1 (factorielle 0))))) - →
(* 4 (* 3 (* 2 (* 1 1))))) - → 24
on remplace à chaque étape « (factorielle n) » par
« (* n factorielle (n-1)) » (en écriture semi-préfixée) jusqu'à arriver à 0, puisque « (factorielle 0) » est remplacé par « 1 ».
Voir aussi
[modifier | modifier le wikicode]- Dans Wikipédia