La récursivité
La récursivité
Définition
La récursivité est le fait pour une méthode de s'appeler
elle même. On parle alors de méthode récursive.
Exemple : Le calcul de la factorielle de N.
N != N*(N-1)*(N-2)*…*2*1, on peut écrire ainsi N != N*(N-1)!
La factorielle de N est définie en fonction de la factorielle de
N-1
A l’opposé, l’itération utilise les structures de contrôle
répétitives comme POUR,TANT QUE, REPETER JUSQU'À
La récursivité
La récursivité
Solution itérative Solution récursive
Fonction factoriel(n:entier):entier Fonction factoriel(n:entier):entier
var Début
n,i,f : entier Si (n=0) alors
Début retourner 1
f 1 Sinon
Pour i de 2 à n faire retourner n* factoriel(n-1)
f f * i FinPour FinSi
Retourner f Fin
Fin
Appel récursif
La récursivité
En C
#include <stdio.h>
int factoriel(int n)
{
if (n == 0)
return 1;
else return n*factoriel(n-1);
void main ()
{
int res;
res = factoriel (5);
printf ("5! = %d\n", res);
}
La récursivité
Empilage du contexte local
Chaque procédure stocke dans une zone mémoire
les paramètres
les variables locales
Cette zone s’appelle la pile car les données sont
empilées lors de l’appel d’une procédure
désempilées à la fin de la procédure
A chaque appel récursif, l’ordinateur empile donc
les variables locales
les paramètres qui doivent changer à chaque appel
La récursivité
Trace d’exécution
Trace de la méthode factoriel avec n = 5
La récursivité
Seul les problèmes dont la solution se base sur une
relation de récurrence avec une condition de sortie
peuvent êtrerésolus de façon récursive
Isoler les cas terminaux pour le problème étudié
Un cas terminal représente un cas où l’on peut donner
directement une valeur à la fonction
Dans la fonction puissance le cas terminal est x0=1
Dans la fonction factoriel 0!=1 est un cas terminal
Le choix entre une solution itérative ou une solution
récursive dépend de la complexité en espace et en
temps et du langage de programmation.
Ex: Cobol n’est pas un langage récursif
La récursivité
Structure d’un sous programme récursif : 3 étapes
1. Trouver une décomposition récursive du problème:
a. Trouver l’élément de récursivité qui permet de définir le cas plus
simple
( exemple: une valeur qui décroît, une taille de données qui
diminue)
b. Exprimer la solution dans le cas général en fonction de la solution
pour le cas plus simple
2. Trouver la condition d’arrêt de la récursivité et la solution
dans
ce cas
Vérifier que la condition d’arrêt est atteinte après un nombre
fini d’appels récursifs dans tous les cas
La récursivité
3. Réunir
les deux étapes précédente dans un seul sous-
programme
La récursivité
Structure d’un sous programme récursif :
Le corps d’un sous-programme récursif est composé
essentiellement de :
une condition d’arrêt
un ou plusieurs appels récursifs, intégrés dans une
structure conditionnelle de la forme (si ...
alors...sinon...finsi).
La récursivité
Syntaxe
Procédure
Procédure nomProcRec(param1:typeParam1,...,paramN:typeParamN)
var
{Déclaration des variables locales}
Début
Si (condition d’arrêt) alors
traitement d’arrêt
Sinon nomProcRec (para1, ...,paraN) {appel récursif}
FinSi
Fin
La récursivité
Syntaxe
Fonction
Fonction nomFonctRec(p1:typeParam1,...,pN:typeParamN):type_retour
var
{Déclaration des variables locales}
Début
Si (condition d’arrêt) alors
Retourner(Expression1)
Sinon
Retourner (nomFonctRec (para1, ...,paraN))
FinSi
Fin
La récursivité
Application 1
Soient A une liste d’entiers représentée par un tableau de N entiers
donnés.
Ecrire une fonction recursive qui retourne la somme des N entiers de A,
La récursivité
La récursivité
La récursivité
La récursivité
La récursivité
La récursivité
La récursivité
Recherche Dichotomique
Définir récursivement une fonction qui indique si un entier x appartient ou
non à un tableau d'entiers T trié par ordre croissant.
Cette fonction utilisera le principe de la dichotomie.
La récursivité
La récursivité
Types de récursivité
Récursivité directe: la récursivité R est directe si
elle est définie en fonction de R, (le module
s’appelle lui-même)
Récursivité indirecte: la récursivité R est
indirecte si elle appelle R1, qui appelle R2,…, qui
appelle Rn qui appelle R
Récursivité croisée: la récursivité R est croisée si elle appelle
R1, qui appelle R
La récursivité
Récursivité double: la récursivité R est double
quand dans la même instruction nous retrouvons
deux appels àla même fonction
La récursivité
Exemple : récursivité double
Calculer la suite de Fibonacci : f0=1, f1=1, fn=fn-2 +
fn-1 pour n>1, (1, 1, 2, 3, 5, 8, 13, 21)
La récursivité
Fonction fibonacci(n:entier):entier
Début
Si (n=0) ou (n=1) alors
retourner 1
Sinon
retourner fibonacci (n-2)+ fibonacci (n-1)
Finsi
Fin
La récursivité
La dérécursivation
C’est la transformation d’un algorithme récursif en
unalgorithme itératif équivalent.
La méthode à suivre dépend du type de récursivité
del’algorithme.
Récursif terminal : Un sous programme est dit récursif
terminal s’il ne contient aucun traitement après un appel
récursif.
Récursif non terminal : un sous programme est récursif non
terminale s’il effectue un traitement après un appel
récursif.
121
La dérécursivation
Dérécursivation d’un sous programme récursif terminal
Procédure récursive Procédure itérative équivalente
Procédure Procédure p_iter(params:type)
p_rec(params:type) Début Début
Si (condition) alors Tant que (Non condition) faire
traitement1 traitement2
Sinon params ← nouv_params
traitement2 FinTantQue
p_rec(nouv_params traitement
) 1 Fin
FinSi
Fin
123
La dérécursivation
Exemple : récursivité terminale (addition de deux entiers
positifs
ou nuls)
Fonction plus ( a , b : entier ) : Fonction
entier Début plus_iter(a,b:entier):entier
Si ( b = 0 ) Alors Début
Retourner ( a ) Tant que (b<>0) faire
Sinon a ← a+1
Retourner plus ( a + 1, b - 1) b ← b-
FinSi 1FinTantQue
Fin Retourner a
Fi
123