Récursivité

Parent Category: Informatique et réseaux Category: Algorithme

La récursivité encore appelée récurrence en mathématique permet de réaliser des traitements répétitifs particulièrement complexes que les structures itératives classiques ne peuvent aborder facilement. Elle permet de simplifier la structure des programmes. On dit qu'il y'a récursivité lorsque la définition d'un objet fait apparaître l'objet lui-même.

 


Quelques exemples d'utilisation de la récursivité

Structure de données récursives

Exemple:

  • Les listes.
  • Les piles.
  • Les files.
  • Les arbres.

Le raisonnement récursif

Le raisonnement récursif comporte deux phases bien distinctes:

  • Une formulation simpliste ou triviale: qui permet d'arrêter les traitements récursif.
  • Une formulation récursive: qui permet de poursuivre le traitement, exemple: tant que la condition est vraie on exécute l'action.

 


Récursivité indirecte

Encore appelée récursivité cachée ou croisée, la récursivité indirecte a lieu lorsqu'une procédure appelle une seconde procédure qui à son tour appelle la première.
Exemples:
f(n) = g(n-1)
g(n) = f(n-1)

 


La récursivité directe

Ici la procédure s'appelle elle-même, la condition importante dans l'utilisation de la récursivité directe est que les objets engendrés par une définition récursive doivent être fini. Ainsi dans une procédure utilisant la récursivité directe on a deux notions:

  • La procédure s'appelle elle-même: on ne commence avec de nouvelle données.
  • Il y'a un texte de fin ou une condition d'arrêt: la procédure doit contenir une construction telle que dans certains cas l'évolution puisse se faire directement sans appel récursif. Pour cela il est souvent préférable d'indiquer le test de fin des appels récursifs en début de procédure. On a donc la formulation suivante:
    Premier cas:
    si condition_fin alors
    instruction
    sinon
    appel récursif
    fin si

    Deuxième cas:
    tant que non(condition_fin) faire
    appel récursif
    fin tant que
    instruction

 


Application

Fonction factorielle

La factorielle d'un nombre entier n est le produit des nombres entiers inférieurs ou égaux à ce nombre n. Cette définition peut se noter de plusieurs façons

  1. 0!=1
    1!=1
    2!=2
    3!=3x2x1
    N!=N(N-1)x...x2x1
  2. N!=1 si N=0
    N!=N(N-1)x...x2x1 si N>0
  3. N!=1 si N=0
    N!=N(N-1)! si N>0

fonction factorielle(N:entier):entier
var p, i: entier
début
si N=0 alors
factorielle ←1
sinon
p ← 1
pour i=1 à N faire
p ← i*P
fin pour
factorielle ← p
fin si
fin

Autre fonction

fonction factorielle(N: entier): entier
debut
si N=0 alors
factorielle ← 1
sinon
factorielle ← n*factorielle(n-1)
fin si
fin

Exécution

F0

F1

F2

F3

F4

N = 3
fact(3)

3*fact(2)
fact(2)

2*fact(1)
fact(1)

1*fact(0)
fact(0)

1

Fonction de Fibonacci

f0 ; f1=1
fn=fn-2+fn-1 si n>1
f(n)=n si n<=1
f(n)=f(n-2)+f(n-1) si n>1

Correction:

fonction fibonacci(n:entier):entier
début
si n<=1 alors
fibonacci ← n
sinon← fibonacci(n-1)+fibonacci(n-2)
fin si
fin