Aller au contenu
Ludicademy
English
Thème Élan
ClairsSombres
S’inscrire

Fiche de révision : La récursivité : un algorithme qui s'appelle lui-même

L’essentiel de la leçon, ce qu’il faut retenir, les pièges et un petit test : une page à relire avant le contrôle.

Ludicademyludicademy.fr · apprendre en jouant, du CP à la Terminale
Fiche de révision · Logique · Tle · algorithmique

La récursivité : un algorithme qui s'appelle lui-même

Objectif : définir une chose à partir d'elle-même sans tourner en rond

L’essentiel

Un algorithme RÉCURSIF résout un problème en s'appelant lui-même sur un problème PLUS PETIT. Cela paraît circulaire, et ce ne l'est pas — à deux conditions strictes, faute desquelles le raisonnement tourne effectivement en rond et le programme avec lui. PREMIÈRE CONDITION : un CAS DE BASE, un cas assez petit pour être résolu sans appel.

À retenir

  • Un algorithme récursif s'appelle sur un problème strictement plus petit
  • Il lui faut un cas de base, sinon la descente ne s'arrête jamais
  • La descente empile les appels, la remontée calcule les résultats en sens inverse
  • La récursivité s'impose sur les structures récursives, pas partout : elle peut coûter très cher

Le tableau à connaître

La factorielle de nLa version itérativeLa version récursive
Le principeMultiplier de 1 jusqu'à n dans une bouclen fois la factorielle de n moins 1
Le cas de baseLe résultat part à 1factorielle(0) vaut 1, sans appel
Ce qui décroîtLe compteur monte vers nL'argument descend vers 0
Ce qu'on litComment on calculeCE QU'EST le résultat

⚠ Attention, piège

  • Récursif ne veut pas dire efficace. La suite de Fibonacci définie récursivement recalcule les mêmes valeurs un nombre exponentiel de fois : fibonacci(50) écrit naïvement demande des milliards d'appels, là où une boucle de cinquante tours suffit.

Exemples

  • Calculons factorielle(4).

Le plan de la leçon

  1. Se définir soi-même, légalement
  2. Deux définitions du même calcul
  3. Dérouler une descente et une remontée
  4. Quand elle s'impose vraiment

Je me teste

  1. Que manque-t-il à « factorielle(n) vaut n fois factorielle(n moins 1) » ?

    1. Un compteur pour les tours de boucle
    2. Le cas de base pour arrêter la descente
    3. Une variable pour stocker le total
  2. Dans le calcul de factorielle(4), quand le premier produit est-il effectué ?

    1. À la remontée, après le cas de base
    2. Avant tout appel, au départ
    3. À la descente, dès le premier appel

Le mot d’Oscar — Définissez-moi « ancêtre ».

Réponses : 1. B · 2. A

La leçon complète, ses exercices et ses jeux : ludicademy.fr/lecon/2415fiche de révision · usage libre en classe et à la maison

Toutes les fiches de révision : par matière et par classe · les fiches d’exercices : la bibliothèque.