Récursivité
La fonction qui s'appelle elle-même : cas de base, appel sur un problème plus petit, pile d'appels, descente et remontée, et la récursion sans fin qui s'arrête sur une erreur.
- 30 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
Récursivité : de quoi s'agit-il ?
Voir la réponse
Technique où une fonction s'appelle elle-même pour résoudre un problème plus petit, de même nature que le problème de départ.
Elle s'écrit en deux morceaux : un cas où la fonction répond directement, et un appel sur une donnée réduite.
fact(4)s'appuie surfact(3), qui s'appuie surfact(2).Que renvoie
fact(4)?
```python
def fact(n):
if n == 0:
return 1
return n * fact(n - 1)`241016120
Voir la réponse
24fact(4)vaut 4 ×fact(3), soit 4 × 3 × 2 × 1 ×fact(0)= 24. Les valeurs reviennent à la remontée : 1, 1, 2, 6, puis 24. Additionner donnerait 10, et 120 estfact(5).Une fonction récursive correcte a un … qui répond sans appel, et chaque appel travaille sur un problème …, de façon à s'en rapprocher.
Voir la réponse
Une fonction récursive correcte a un cas de base qui répond sans appel, et chaque appel travaille sur un problème plus petit, de façon à s'en rapprocher.
Si l'un des deux manque, la chaîne d'appels ne se termine jamais : le cas de base la coupe, la réduction du problème garantit qu'on l'atteint.
Cas de base : de quoi s'agit-il ?
Voir la réponse
Cas où la fonction renvoie sa réponse directement, sans faire de nouvel appel : c'est lui qui arrête la chaîne d'appels.
Pour la factorielle,
fact(0)renvoie 1. Sans ce cas, aucun appel ne peut jamais rendre de valeur.