Téléchargement d'épreuves

et

Cours gratuits

Récursivité

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

Consultez gratuitement nos différents cours

  • L’effet photoélectrique (Science physique)

    L'effet photoélectrique est un phénomène d'extraction des électrons sous l'action d'une réaction lumineuse. Les lois de l'effet photoélectrique     Une cellule photoémissive est une ampoule de verre transparente à ultraviolet scellé et dans laquelle on a fait un vide poussé. Elle est constituée d'une cathode métallique C et d'une anode. Si on envoie sur la cellule une lumière monochromatique de longueur d'onde de plus en plus petite, on constate qu'il y'a apparition d'un courant dans le circuit...

    Lire la suite : L’effet photoélectrique

  • Introduction générale au réseau Internet (Réseaux informatiques)

    Généralité Le réseau Internet est né le 21 Novembre 1969, jour où 3 universités Américaines s'interconnectaient pour communiquer à travers des ordinateurs. C'était la naissance du réseau ARPARNET, ancêtre de l'Internet actuel. Le "Net" signifie filet ou "maillage". Dans le réseau Internet, les messages sont découpés chacun en paquet. Chaque paquet contient une partie de l'information utile, celui-ci choisit sont itinéraire de façon aléatoire et peut réagir de façon à éviter tout goulot...

    Lire la suite : Introduction générale au réseau Internet

  • La lumière (Science physique)

    Dans la nuit une multitude de source lumineuse artificielle brille dans la ville. Pour voir ces sources, il faut utiliser l'oeil qui est notre récepteur de lumière. Dans ce document nous allons étudier brièvement la propagation de la lumière, la détection de la lumière et les couleurs.   Sources et réception de lumière C'est un corps qui produit la lumière: soleil, étoile, feu tricolore. Source primaire: Elle produit elle-même la lumière Source secondaire: Elle renvoie la lumière qu'elle reçoit....

    Lire la suite : La lumière

  • Les causes et les doctrines impérialistes (Histoire)

    A la suite des bouleversements qui ont marqué l'Europe, la fin du 19es voit apparaître les germes d'une politique de domination de certains peuples sur d'autres et notamment la domination des Européens sur le reste du monde, c'est l'impérialisme. Définition et causes L'impérialisme est une doctrine qui préconise la domination politique et économique des Etats les plus forts sur ceux techniquement faibles trop en retard ou trop divisés pour résister. Ces dominations peuvent être territoriales...

    Lire la suite : Les causes et les doctrines impérialistes