Programmation Scheme/Récursivité

Programmation Scheme

1. Introduction
2. Notions élémentaires
3. Syntaxe de base
4. Grammaire de base
5. La boucle d'évaluation
6. Variables globales et variables locales
7. 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

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

Dans Wikipédia

• Récursivité

---

Variables globales et variables locales < ↑ >