Itératif contre récursif
Le même calcul écrit avec une boucle ou avec des appels récursifs : équivalence, mémoire de la pile, calculs refaits, passage d'une forme à l'autre et critères de choix.
- 25 cartes
- 6 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
- Mises en situation
- Comprendre
Quelques cartes du deck
Itération : de quoi s'agit-il ?
Voir la réponse
Répétition d'un bloc d'instructions par une boucle, avec des variables qui évoluent à chaque tour jusqu'à la fin du calcul.
La boucle garde son état dans quelques variables, comme
rdansr = r * n; la version récursive le garde dans les paramètres de chaque appel.Quelle fonction récursive renvoie la même valeur que
fpour tout entier n ≥ 1 ?
```python
def f(n):
r = 1
while n > 1:
r = r * n
n = n - 1
return r`def g(n): return 1 if n <= 1 else n * g(n - 1)def g(n): return 1 if n <= 1 else n + g(n - 1)def g(n): return 1 if n <= 1 else g(n - 1)def g(n): return 0 if n <= 1 else n * g(n - 1)
Voir la réponse
def g(n): return 1 if n <= 1 else n * g(n - 1)La boucle multiplie
rpar n, n - 1, …, 2 en partant de 1 : c'est la factorielle. Ler = 1initial devient le cas de base, etr = r * ndevientn * g(n - 1). Avec+on additionne, sansn *le résultat reste 1, et un cas de base à 0 annule tout.Tout calcul écrit avec une boucle peut s'écrire avec des appels récursifs, et inversement : les deux formes sont …, mais la forme récursive occupe de la place sur la ….
Voir la réponse
Tout calcul écrit avec une boucle peut s'écrire avec des appels récursifs, et inversement : les deux formes sont équivalentes, mais la forme récursive occupe de la place sur la pile d'appels.
Pour passer d'une forme récursive à une boucle, les paramètres deviennent des variables mises à jour à chaque tour. Pour des structures complexes, on peut avoir à gérer soi-même une pile.
Débordement de pile : de quoi s'agit-il ?
Voir la réponse
Erreur qui survient quand trop d'appels de fonction sont imbriqués en même temps et que la zone de mémoire qui les garde est pleine.
En Python, l'interpréteur s'arrête avant, sur
RecursionError. En C ou en Java, le programme s'interrompt, par unStackOverflowErroren Java.