Récursivité en programmation

Étudier le code python ci-dessous. Que fait la fonction compte(n) ?

def compte(n):
   """n est un entier positif"""
   s=0
   for i in range(n+1):
     s=s+i
   return s

print(compte(12))

Quelle différence y a-t-il avec le code suivant ?

def compteRec(n):
    """n est un entier positif"""
    if n==0:
        return 0
    else:
        return n+compteRec(n-1)

print(compteRec(12))

Explications

La fonction compte(n) calcule la somme des entiers de 0 à n et renvoie sa valeur.

La fonction compteRec(n) renvoie 0 si n vaut 0, ou renvoie n additionné à compteRec(n-1). Cette fonction calcule donc n + (n-1) + (n-2) + ... + 0.

En détail :

• compteRec(5) = 5 + compteRec(4)
  • compteRec(4) = 4 + compteRec(3)
    • compteRec(3) = 3 + compteRec(2)
      • compteRec(2) = 2 + compteRec(1)
        • compteRec(1) = 1 + compteRec(0)
          • compteRec(0) = 0
        • compteRec(1) = 1 + 0 = 1
      • compteRec(2) = 2 + 1 = 3
    • compteRec(3) = 3 + 3 = 6
  • compteRec(4) = 4 + 6 = 10
• compteRec(5) = 5 + 10 = 15

Fonction récursive

On dit qu'une fonction est récursive lorsqu'elle fait appel à elle même dans le corps de sa définition.

Produit

Si l'on veut calculer le produit de 3 par 4 (sans multiplication), on peut tout simplement calculer \(3 + 3 \times 3\) sauf que \(3 \times 3 = 3 + 3 \times 2\), etc...

Recopier et compléter le code ci-dessous afin que la fonction produit(m, n) renvoie le produit des entiers naturels m et n.

Et bien sûr, faites des tests !

def produit(m,n):
    """
    Calcule le produit de m et n, deux entiers naturels.
    """
    if n == 0:
        return ...
    else:
        return ...

Réponse

def produit(m,n):
    """
    Calcule le produit de m et n, deux entiers naturels.
    """
    if n==0:
        return 0
    else:
        return m + produit(m, n - 1)

Attention toutefois à respecter certaines conditions :

• Une fonction récursive doit contenir au moins une condition d'arrêt, sinon le programme va boucler indéfiniment !
• Les valeurs qui sont passées en paramètres aux appels récursifs de la fonction doivent être différentes, sinon la fonction s'exécutera toujours de manière identique et la condition d'arrêt ne pourra jamais être vérifiée !
• Les valeurs passées en paramètres doivent satisfaire les conditions d'arrêt après un nombre fini d'appels, sinon le programme va boucler indéfiniment et générer une erreur du type : RecursionError