Terminale · Numérique et sciences informatiques

Récursivité

Savoir écrire un programme récursif en identifiant un cas de base qui arrête les appels et un cas récursif qui réduit le problème.

Aperçu gratuit
Illustration de la fiche « Récursivité »

Les points essentiels

  • Une fonction récursive est une fonction qui s'appelle elle-même dans son propre corps.
  • Une fonction récursive correcte contient toujours au moins un cas de base : une situation simple que l'on traite sans rappeler la fonction.

Les mots à connaître

Fonction récursive
Fonction dont le code contient un appel à elle-même.
Cas de base
Situation traitée directement, sans appel récursif, qui arrête la suite des appels.

Un exemple pour comprendre

Écris en Python une fonction récursive factorielle(n) qui renvoie n! pour n entier positif, avec 0! = 1.

def factorielle(n): if n == 0: return 1 return n * factorielle(n - 1) Le cas de base est n == 0 : on renvoie 1 sans rappeler la fonction. Le cas récursif est n * factorielle(n - 1) : l'appel porte sur n - 1, donc un nombre plus petit, qui se rapproche de 0. Pour n = 3 : factorielle(3) appelle factorielle(2), qui appelle factorielle(1), qui appelle factorielle(0). Celle-ci renvoie 1. Les résultats remontent : 1 × 1 = 1, puis 2 × 1 = 2, puis 3 × 2 = 6.

Première page de l’Essentiel : Récursivité
Ketty