Objectifs d'apprentissage

À la fin de cette section, vous devriez être en mesure de :

• Identifier un cas récursif et un cas de base dans un algorithme récursif.
• Démontrer comment calculer une solution récursive pour la fonction factorielle.

Calcul d'une factorielle

La factorielle d'un entier strictement positif est définie comme le produit de cet entier par tous les entiers strictement positifs qui lui sont inférieurs.

Ex. : 5! = 5 * 4 * 3 * 2 * 1

Écrite sous la forme d'une équation générale pour un entier strictement positif n: n! = n * (n - 1) * (n - 2) * . . . * 1

La formule ci-dessus pour la factorielle de n aboutit à une formule récursive : n! = n * (n - 1)!

Ainsi, la factorielle de n dépend de la valeur de la factorielle de n - 1. On peut trouver la factorielle de n en répétant la factorielle de n - 1 jusqu'à ce que (n - 1)! = 1! (sachant que 1! = 1). Ce résultat peut être utilisé pour construire la solution globale, comme le montre l'animation ci-dessous.

Définir une fonction récursive

Les algorithmes récursifs sont écrits en Python sous forme de fonctions. Dans une fonction récursive, différentes actions sont exécutées selon la valeur du paramètre d'entrée. Un aspect fondamental d'une fonction récursive est que la fonction doit s'appeler elle-même.

Une valeur à laquelle s'applique la récursivité est appelée le cas récursif (recursive case). Dans le cas récursif, la fonction s'appelle elle-même avec une portion plus petite du paramètre d'entrée. Ex. : Dans la fonction récursive factorial(), le paramètre initial est un entier n. Dans le cas récursif de la fonction, l'argument passé à factorial() est n - 1, qui est plus petit que n.

Une valeur de n pour laquelle la solution est connue est appelée le cas de base (base case). Le cas de base arrête la récursivité. Un algorithme récursif doit comporter un cas de base ; sinon, l'algorithme peut entraîner un calcul infini.

Pour calculer une factorielle, une fonction récursive, factorial(), est définie avec un paramètre d'entrée entier, n. Lorsque n > 1, le cas récursif s'applique. La fonction factorial() s'appelle elle-même avec un argument plus petit, n - 1. Lorsque n == 1, la solution est connue car 1! vaut 1 ; par conséquent, n == 1 est un cas de base.

Remarque : 0! est défini comme valant 1 ; par conséquent, n == 0 est un second cas de base pour factorial(). Lorsque n < 1, une erreur est renvoyée.

def rec_fact(n):
  return n * rec_fact(n - 1)

def rec_fact(n):
  if n < 0:
    print("error")
  elif n == 0:
    return n
  else:
    return n * rec_fact(n - 1)

def rec_fact(n):
  if n < 0:
    print("error")
  elif n == 0:
    return 1
  else:
    return n * rec_fact(n - 1)

def rec_fact(n):
  if n < 0:
    return -1
  else:
    return n * rec_fact(n - 1)