Aller au contenu

Exercices – Récursivité : principe

BTS SIO SISR 2e année – Pour aller plus loin – S06

Note

Comment travailler. Cherche d'abord sur papier. Ouvre ensuite « Voir la réponse » pour te corriger. Aucune réponse sans justification n'est complète.

Exercice 1 – Dérouler fact(4)

Écrire les appels successifs de fact(4) et la valeur renvoyée. Combien d'appels ?

Voir la réponse

fact(4) = 4 × fact(3), fact(3) = 3 × fact(2), fact(2) = 2 × fact(1), fact(1) = 1 × fact(0), fact(0) = 1. Remontée : 1, 1, 2, 6, 24. Il y a 5 appels (de 4 à 0).

Exercice 2 – Une définition récursive

On veut calculer \(S(n) = 1^2 + 2^2 + \dots + n^2\). Donner le cas de base, le cas récursif, puis \(S(4)\).

Voir la réponse

Cas de base : \(S(0) = 0\). Cas récursif : \(S(n) = n^2 + S(n-1)\). Donc \(S(1) = 1\), \(S(2) = 5\), \(S(3) = 14\), \(S(4) = 30\).

Exercice 3 – Deux erreurs

Que se passe-t-il pour chaque fonction ? Corriger.

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

def g(n):
    if n == 0:
        return 0
    return g(n + 1)
Voir la réponse

f n'a pas de cas de base : les appels ne s'arrêtent jamais (RecursionError). Correction : ajouter if n == 0: return 1. g a un cas de base mais l'appel g(n + 1) s'éloigne de 0 : le variant ne décroît pas. Correction : g(n - 1).

Exercice 4 – Algorithme d'Euclide

Dérouler pgcd(252, 105). Quel est le variant ?

Voir la réponse

pgcd(252, 105) → pgcd(105, 42) → pgcd(42, 21) → pgcd(21, 0) : renvoie 21. Les seconds arguments 105, 42, 21, 0 décroissent strictement : le variant est b.

Exercice 5 – Nombre d'appels

Combien d'appels (le premier compris) fait puissance(2, 10) ? Et puissance(x, n) ?

Voir la réponse

Les appels portent sur n = 10, 9, …, 0 : 11 appels. Pour puissance(x, n) : \(n + 1\) appels.

Exercice 6 – Conversion binaire

Dérouler binaire(13). Que renvoie binaire(10) ?

Voir la réponse

binaire(13) = binaire(6) + "1", binaire(6) = binaire(3) + "0", binaire(3) = binaire(1) + "1" = "11". Donc "110" puis "1101". Pour 10 : binaire(5) + "0" avec binaire(5) = binaire(2) + "1" et binaire(2) = binaire(1) + "0" = "10" : on obtient "1010".

Exercice 7 – Version itérative

Écrire une version itérative de puissance(x, n). Les deux versions donnent-elles le même résultat ? Laquelle risque une RecursionError pour n = 5000 ?

Voir la réponse 
def puissance_iter(x, n):
    p = 1
    for _ in range(n):
        p = p * x
    return p

Même résultat. La version récursive risque une RecursionError pour \(n = 5\,000\) (la limite par défaut de Python est d'environ 1 000 appels imbriqués). La version itérative n'a pas ce problème.

Je sais faire

Coche honnêtement ; ce que tu ne coches pas se reprend avant la séance suivante.

  • Nommer cas de base, cas récursif et variant
  • Dérouler une exécution récursive
  • Repérer une erreur de terminaison
  • Écrire la version itérative équivalente

Ce que je dois reprendre : ______________________

Ma question à poser à l'enseignant : ______________________