Recursion: base case and recursive case · Récursion : cas de base et cas récursif
A function that calls itself
- Recursion is when a function calls itself to solve a smaller version of the same problem.
- It needs two parts: a base case that stops, and a recursive case that shrinks the problem.
- Without a base case, it would call itself forever and crash.
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.
The base case
- The base case is the smallest problem you can answer directly, with no more calls.
- For factorial,
0!and1!are both1— that is the base case. - Always handle the base case first, so the recursion has somewhere to stop.
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.
The recursive case
- The recursive case solves the problem using the answer to a smaller one.
n! = n × (n - 1)!, sofactorial(n)returnsn * factorial(n - 1).- Each call must move closer to the base case, or it will never stop.
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;
}
Recursion over an array
- You can recurse along an array by passing an index that moves forward each call.
- The base case is "the index has reached the end" (return
0for a sum). - The recursive case is
a[i] + sum(a, i + 1, n)— this item plus the sum of the rest.
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.
Common mistakes
- Recursion needs a base case, or the call stack overflows.
- Each call must move closer to the base case.
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.
Now you try
- Write the base case first, then the recursive case that calls itself on a smaller input.
- Keep test values small so the numbers stay inside an
int. - Do not write a
main— the checker provides one.
À 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 · La récursion remonte
Calls split to a base case, then values return up. · Les appels se scindent vers un cas de base, puis les valeurs remontent.
Complete int factorial(int n) using recursion: return 1 for n <= 1 (the base case), otherwise n * factorial(n - 1). Do not · non write a main. · Complétez int factorial(int n) en utilisant la récursion : retournez 1 pour n <= 1 (le cas de base), sinon n * factorial(n - 1). Ne pas écrire de main.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Complete int power(int base, int exp) using recursion (assume exp >= 0): base to the power 0 is 1, otherwise base * power(base, exp - 1). Do not · non write a main. · Complétez int power(int base, int exp) en utilisant la récursion (supposez exp >= 0) : base à la puissance 0 est 1, sinon base * power(base, exp - 1). Ne pas écrire de main.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
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 returns · rendements 0. Do not · non write a main. · Complétez int array_sum(const int a[], int i, int n) en utilisant la récursion : il retourne la somme de a[i] jusqu'à a[n-1]. Cas de base : i >= n retourne 0. Ne pas écrire de main.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.