Bases de la récursivité

Fait partie de la section Fundamentals du Journey C de Coddy — leçon 50 sur 63.

La récursion est une technique où une fonction s'appelle elle-même pour résoudre un problème. C'est comme résoudre un gros problème en le décomposant en problèmes plus petits et similaires.

Examinons une fonction récursive simple qui calcule la factorielle :

int factorial(int n) {
    // Cas de base : la factorielle de 0 ou 1 est 1
    if (n <= 1) {
        return 1;
    }
    
    // Cas récursif : n! = n * (n-1)!
    return n * factorial(n - 1);
}

Chaque fonction récursive a besoin de :

Un cas de base pour arrêter la récursion
Un cas récursif qui se rapproche du cas de base

Par exemple, le calcul de factorial(3) :

factorial(3) appelle factorial(2)
factorial(2) appelle factorial(1)
factorial(1) retourne 1 (cas de base)

factorial(2) retourne 2 * 1 = 2
factorial(3) retourne 3 * 2 = 6

Défi

Facile

Créez une fonction nommée sumToN qui utilise la récursion pour calculer la somme des nombres de 1 à n.

Par exemple :

sumToN(3) devrait retourner 6 (1 + 2 + 3)
sumToN(5) devrait retourner 15 (1 + 2 + 3 + 4 + 5)

Votre fonction devrait :

Utiliser un cas de base lorsque n est 1 (retourner 1)
Sinon, retourner n plus la somme des nombres de 1 à (n-1)

Aide-mémoire

La récursion est une technique où une fonction s'appelle elle-même pour résoudre un problème en le décomposant en problèmes plus petits et similaires.

Chaque fonction récursive a besoin de :

Un cas de base pour arrêter la récursion
Un cas récursif qui se rapproche du cas de base

Exemple - fonction factorielle :

int factorial(int n) {
    // Cas de base : la factorielle de 0 ou 1 est 1
    if (n <= 1) {
        return 1;
    }
    
    // Cas récursif : n! = n * (n-1)!
    return n * factorial(n - 1);
}

Comment factorial(3) s'exécute :

factorial(3) appelle factorial(2)
factorial(2) appelle factorial(1)
factorial(1) retourne 1 (cas de base)
factorial(2) retourne 2 * 1 = 2
factorial(3) retourne 3 * 2 = 6

Essayez vous-même

#include <stdio.h>

// Écrivez votre fonction sumToN ici

// Ne modifiez pas la fonction main()
int main() {
    int n;
    scanf("%d", &n);
    
    printf("%d", sumToN(n));
    return 0;
}

Testez-vous

Cette leçon comprend un petit quiz. Commencez la leçon pour y répondre et suivre votre progression.

Toutes les leçons de Fundamentals

1Introduction

Langage C Hello World !Commentaires Structure de base d'un programme

4Structures de contrôle

L'instruction If If - Else Else-If Switch Case Opérateur ternaire Défi récapitulatif If - Else imbriqués

7Fonctions

Déclarer une fonction Types de retour Paramètres Défi récapitulatif n°1Bases de la récursivitéPrototypes de fonction Défi récapitulatif n°2