Algorithmes C/C++

La récursivité et la pile d'appels en C et C++

Dans cette leçon, vous allez calculer une factorielle avec une fonction récursive et comprendre le cas de base et le coût mémoire de la récursivité.

Introduction

La récursivité consiste à résoudre un problème en le ramenant à un problème plus petit du même type. Toute fonction récursive a besoin d'un cas de base (base case), et chaque appel doit s'en rapprocher, sinon le programme rappelle la fonction indéfiniment.

Points importants

Testez avec une entrée vide, un seul élément, des doublons et des données déjà triées.
Rendez d'abord le code correct, optimisez ensuite.
Dans du vrai code, préférez les fonctions toutes prêtes de la bibliothèque standard.

Voir comment ça marche

Appuyez sur Étape pour suivre chaque appel. Les nouveaux appels vont sur la pile d'appels, et chacun renvoie sa valeur à l'appel qui l'a lancé.

Exemples de code C et C++

Exécuter →

main.c

#include <stdio.h>

unsigned long long factorial(unsigned number) {
    return number < 2 ? 1 : number * factorial(number - 1);
}

int main(void) {
    printf("%llu\n", factorial(6));
}

Résultat de l’exécution

C++

Exécuter →

main.cpp

#include <iostream>

constexpr unsigned long long factorial(unsigned number) {
    return number < 2 ? 1 : number * factorial(number - 1);
}

int main() {
    constexpr auto value = factorial(6);
    std::cout << value << '\n';
}

Résultat de l’exécution

Comparaison entre C et C++

La fonction factorial renvoie 1 quand number est inférieur à 2, c'est le cas de base, et sinon renvoie number * factorial(number - 1). Chaque appel occupe un peu plus de place sur la pile d'appels (call stack), l'algorithme utilise donc O(n) en temps et O(n) en pile. La version C++ marque la fonction constexpr, la valeur peut donc être calculée dès la compilation. Avec de grandes entrées, il faut valider les données et préférer en général une boucle à la récursivité.

Les boucles, les pointeurs, les longueurs et les tampons temporaires sont écrits explicitement.

C++

Les itérateurs et les algorithmes standard séparent le traitement de la façon dont les données sont stockées.

Exercices d'approfondissement

Exécutez les deux versions, puis modifiez le code pour observer la différence de sécurité qu'apporte chaque langage.

Déroulez chaque comparaison sur papier.
Testez avec des doublons et des valeurs très grandes et très petites.
Mesurez le temps d'exécution de votre code et comparez-le à la bibliothèque standard.

S'entraîner avec un défi

Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.

Tous les défis