TP Python – Premières fonctions récursives

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

Note

Comment ce TP fonctionne. Chaque exercice a un éditeur Python intégré à la page (il s'exécute dans ton navigateur, rien à installer). Avant de lancer, écris sur ta feuille ce que tu anticipes (« J'anticipe »). Puis lance et compare. Le bouton Valider exécute des tests : un test réussi ne dispense pas de comprendre pourquoi.

Exercice A – Factorielle

Écris factorielle(n) (\(n \ge 0\)) sans boucle, avec un cas de base et un appel récursif.

J'anticipe. Combien d'appels pour factorielle(5) ?

###

Lancer assert factorielle(0) == 1bksl-nlassert factorielle(1) == 1bksl-nlassert factorielle(5) == 120bksl-nlassert factorielle(10) == 3628800bksl-nlassert all(factorielle(k) == k py-str factorielle(k - 1) for k in range(1, 20))bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def factorielle(n):bksl-nl """n! pour n >= 0, de facon recursive."""bksl-nl ...bksl-nlbksl-nl

---

---

Je comprends. Quel est le variant ? Que se passerait-il en appelant factorielle(-1) ?

Exercice B – Somme des carrés

Écris somme_carres(n) qui renvoie \(1^2 + \dots + n^2\), de façon récursive (exercice 2).

###

Lancer assert sommepy-undcarres(0) == 0bksl-nlassert sommepy-undcarres(1) == 1bksl-nlassert sommepy-undcarres(4) == 30bksl-nlassert all(sommepy-undcarres(k) == k py-str (k + 1) py-str (2 py-str k + 1) // 6 for k in range(0, 100))bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def sommepy-undcarres(n):bksl-nl """1^2 + ... + n^2, de facon recursive."""bksl-nl ...bksl-nlbksl-nl

---

---

Exercice C – Puissance

Écris puissance(x, n) (\(n \ge 0\)) qui renvoie \(x^n\) de façon récursive, sans utiliser **.

###

Lancer assert puissance(2, 10) == 1024bksl-nlassert puissance(5, 0) == 1bksl-nlassert puissance(3, 1) == 3bksl-nlassert puissance(-2, 3) == -8bksl-nlassert all(puissance(a, b) == a py-strpy-str b for a in range(-4, 5) for b in range(0, 12))bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def puissance(x, n):bksl-nl """x puissance n (n >= 0), de facon recursive, sans py-strpy-str."""bksl-nl ...bksl-nlbksl-nl

---

---

Exercice D – Algorithme d'Euclide

Écris pgcd(a, b) (entiers positifs ou nuls) avec l'algorithme d'Euclide récursif : si b == 0, le PGCD est a ; sinon c'est pgcd(b, a % b).

J'anticipe. Écris sur ta feuille les appels de pgcd(252, 105).

###

Lancer assert pgcd(84, 36) == 12bksl-nlassert pgcd(252, 105) == 21bksl-nlassert pgcd(7, 0) == 7bksl-nlassert pgcd(0, 5) == 5bksl-nlassert all(pgcd(a, b) == py-undpy-undimportpy-undpy-und('math').gcd(a, b) for a in range(0, 40) for b in range(0, 40))bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def pgcd(a, b):bksl-nl """PGCD par l'algorithme d'Euclide, de facon recursive."""bksl-nl ...bksl-nlbksl-nl

---

---

Je comprends. Quel est le variant ? Pourquoi décroît-il strictement ?

Exercice E – Écriture en binaire

Écris binaire(n) (\(n \ge 0\)) qui renvoie l'écriture de n en base 2 sous forme de chaîne, de façon récursive : si n < 2, c'est str(n) ; sinon binaire(n // 2) suivi du dernier bit n % 2.

J'anticipe. Que renvoie binaire(10) (exercice 6) ?

###

Lancer assert binaire(0) == '0'bksl-nlassert binaire(1) == '1'bksl-nlassert binaire(13) == '1101'bksl-nlassert binaire(10) == '1010'bksl-nlassert all(binaire(k) == bin(k)[2:] for k in range(0, 300))bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def binaire(n):bksl-nl """Ecriture binaire de n (chaine), de facon recursive."""bksl-nl ...bksl-nlbksl-nl

---

---