Recursion: base case and recursive case
Une fonction qui s'appelle elle-même
- La récursion est quand une fonction s'appelle elle-même pour résoudre une version plus petite du même problème.
- Elle a besoin de deux parties : un cas de base qui s'arrête, et un cas récursif qui réduit le problème.
- Sans cas de base, elle s'appellerait indéfiniment et planterait.
Le cas de base
- Le cas de base est le plus petit problème que vous pouvez répondre directement, sans appels supplémentaires.
- Pour factorielle,
0!et1!valent tous deux1— c'est le cas de base. - G toujour le cas de base en premier, pour que la récursion ait quelque part où s'arrêter.
Le cas récursif
- Le cas récursif résout le problème en utilisant la réponse d'un problème plus petit.
n! = n × (n - 1)!, doncfactorial(n)retournen * factorial(n - 1).- Chaque appel doit se rapprocher du cas de base, sinon il ne s'arrêtera jamais.
#include <stdio.h>
int factorial(int n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case
}
int main(void) {
printf("%d\n", factorial(5)); // 120
return 0;
}
Récursion sur un tableau
- Vous pouvez récursiver sur un tableau en passant un index qui avance à chaque appel.
- Le cas de base est "l'index a atteint la fin" (retourner
0pour une somme). - Le cas récursif est
a[i] + sum(a, i + 1, n)— cet élément plus la somme du reste.
Erreurs courantes
- La récursion nécessite un cas de base, sinon la pile d'appels déborde.
- Chaque appel doit se rapprocher du cas de base.
À vous maintenant
- Écrivez d'abord le cas de base, puis le cas récursif qui s'appelle lui-même sur une entrée plus petite.
- Gardez les valeurs de test petites pour que les nombres restent dans un
int. - N'écrivez pas de
main— le vérificateur en fournit une.
Recursion returns up
Calls split to a base case, then values return up.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
Complete int factorial(int n) using recursion: return 1 for n <= 1 (the base case), otherwise n * factorial(n - 1). Do non write a main.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
Complete int power(int base, int exp) using recursion (assume exp >= 0): base to the power 0 est 1, otherwise base * power(base, exp - 1). Do non write a main.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
Complete int array_sum(const int a[], int i, int n) using recursion: it returns the sum of a[i] up to a[n-1]. Base case: i >= n rendements 0. Do non write a main.
Cliquez sur Exécuter pour voir le résultat ici.