Bases de la récursivité

Fait partie de la section Fondamentaux du Journey C de Coddy. Leçon 50 sur 63.

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

Examinons une simple fonction récursive 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);
}

Toute 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, calculons factorial(3) :

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

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

Défi

Facile

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

Par exemple :

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

Votre fonction doit :

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

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 Fondamentaux

1Introduction

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

4Flux de contrôle

Instruction if If - Else Else-If Cas switch Opérateur conditionnel ternaire Défi récapitulatif If - Else imbriqué

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

Entraînez-vous par vous-même : Compilateur C en ligne