← HUB ✦ Holberton School — C Programming ✦

RECURSION
∞ LEVEL UP

une fonction qui s'appelle elle-même

LVL 4
C'EST QUOI LA RÉCURSION ?
🌀 DÉFINITION

La récursion c'est quand une fonction s'appelle elle-même pour résoudre un problème en le décomposant en sous-problèmes plus petits.

Toute fonction récursive a obligatoirement 2 parties :

Le cas de base (Base Case)

La condition d'arrêt. Sans ça → boucle infinie → stack overflow. C'est le MUR qui stoppe la récursion.

Le cas récursif (Recursive Case)

L'appel à soi-même avec un argument plus petit. On se rapproche du cas de base à chaque appel.

🕹️ ANALOGIE GAMING

Dans Portal, tu places un portail d'entrée et un portail de sortie. La récursion c'est pareil — tu entres dans la fonction (portail), tu ressors du même endroit mais avec un état différent. Le cas de base c'est le mur qui n'a pas de portail — il stoppe le voyage.

LE SQUELETTE — À MÉMORISER
🗺️ STRUCTURE DE BASE
type ma_fonction(type param)
{
    /* 1. CAS DE BASE — condition d'arrêt */
    if (param == cas_terminal)
        return (valeur_finale);

    /* 2. CAS RÉCURSIF — appel avec param plus petit */
    return (ma_fonction(param - 1));
}
Sans cas de base → la fonction s'appelle à l'infini → Segmentation Fault (stack overflow).
EXEMPLES CONCRETS — LES BOSS FIGHTS
⚔️ BOSS 1 — FACTORIELLE
⭐ LVL 1 — Facile

Calcule n! = n × (n-1) × (n-2) × ... × 1. Ex: 5! = 120

int factorial(int n)
{
    /* Cas de base */
    if (n <= 1)
        return (1);

    /* Cas récursif */
    return (n * factorial(n - 1));
}

/* factorial(4) → 4 * factorial(3)
                      → 3 * factorial(2)
                          → 2 * factorial(1)
                              → 1  ← cas de base */
🕹️ ANALOGIE GAMING

C'est comme ouvrir des coffres imbriqués dans Zelda. Le coffre 4 contient le coffre 3, qui contient le coffre 2, qui contient le coffre 1. Le dernier coffre (cas de base) contient le vrai trésor — tu remontes en multipliant à chaque ouverture.

🐲 BOSS 2 — PUISSANCE
⭐⭐ LVL 2 — Intermédiaire

Calcule base^exp de façon récursive.

int power(int base, int exp)
{
    /* Cas de base */
    if (exp == 0)
        return (1);       /* tout^0 = 1 */

    /* Cas récursif */
    return (base * power(base, exp - 1));
}

/* power(2, 4) = 2 * power(2, 3)
              = 2 * 2 * power(2, 2)
              = 2 * 2 * 2 * power(2, 1)
              = 2 * 2 * 2 * 2 * power(2, 0)
              = 2 * 2 * 2 * 2 * 1 = 16 */
👑 BOSS FINAL — SUITE DE FIBONACCI
⭐⭐⭐ LVL 3 — Holberton Style

Calcule le nème terme de Fibonacci : 0, 1, 1, 2, 3, 5, 8, 13, 21...

int fibonacci(int n)
{
    /* Deux cas de base */
    if (n == 0)
        return (0);
    if (n == 1)
        return (1);

    /* Cas récursif — deux appels récursifs ! */
    return (fibonacci(n - 1) + fibonacci(n - 2));
}

/* fibonacci(5) :
   fib(4)          + fib(3)
   fib(3)+fib(2)   + fib(2)+fib(1)
   ... arbre binaire d'appels */
Fibonacci récursif recalcule les mêmes valeurs des dizaines de fois. Pour n > 30 c'est très lent — préférer la version itérative en prod.
LA CALL STACK — CE QUI SE PASSE EN MÉMOIRE
📚 VISUALISATION DE factorial(4)

À chaque appel récursif, une nouvelle stack frame est empilée en mémoire :

▼ DESCENTE (appels)

factorial(4) attend 4 * ? en attente...
factorial(3) attend 3 * ? en attente...
factorial(2) attend 2 * ? en attente...
factorial(1) retourne 1 ✅ CAS DE BASE

▲ REMONTÉE (retours)

/* La pile se dépile dans l'ordre inverse */
factorial(1) → 1
factorial(2) → 2 * 1  = 2
factorial(3) → 3 * 2  = 6
factorial(4) → 4 * 6  = 24  ← résultat final
🕹️ ANALOGIE GAMING

C'est le système de save states dans un émulateur. À chaque appel récursif tu fais un save state (nouvelle frame). Quand tu atteins le cas de base, tu load les saves en sens inverse pour calculer le résultat final.

RÈGLES CRITIQUES — NE MEURS PAS BÊTEMENT
💀 LES GAME OVER
  • Oublier le cas de base → Segfault
  • Cas de base jamais atteint → boucle infinie
  • Pas de progression vers le cas de base → stack overflow
  • Trop d'appels récursifs → stack overflow
  • Modifier un paramètre global → effets de bord
🏆 LES SPEEDRUN TIPS
  • Toujours écrire le cas de base EN PREMIER
  • Vérifier que le param se rapproche du cas de base
  • Tester avec de petites valeurs d'abord
  • Récursion = élégant mais coûteux en mémoire
  • Préférer l'itération pour les grandes valeurs
RÉCURSION VS ITÉRATION
⚖️ MÊME RÉSULTAT, APPROCHE DIFFÉRENTE

RÉCURSIF

int sum_rec(int n)
{
    if (n == 0)
        return (0);
    return (n + sum_rec(n - 1));
}

ITÉRATIF

int sum_iter(int n)
{
    int sum = 0;
    while (n > 0)
        sum += n--;
    return (sum);
}
CRITÈRERÉCURSIONITÉRATION
Lisibilité ✅ Plus claire Parfois verbose
Mémoire ⚠️ Stack frames ✅ O(1)
Performance ⚠️ Overhead ✅ Plus rapide
Cas d'usage idéal Arbres, fractales Tableaux, compteurs
EXEMPLE HOLBERTON — _STRLEN RÉCURSIF
🎓 TYPE D'EXO QUE TU AURAS

Holberton te demandera souvent de réécrire des fonctions standard en récursif :

/* _strlen récursif — sans boucle, sans variable locale */
int _strlen(char *s)
{
    if (*s == '\0')    /* cas de base : fin de string */
        return (0);
    return (1 + _strlen(s + 1)); /* avance d'un char */
}

/* _puts récursif */
void _puts(char *str)
{
    if (*str == '\0')
    {
        putchar('\n');
        return;
    }
    putchar(*str);
    _puts(str + 1);
}

/* _strcmp récursif */
int _strcmp(char *s1, char *s2)
{
    if (*s1 == '\0' || *s1 != *s2)
        return (*s1 - *s2);
    return (_strcmp(s1 + 1, s2 + 1));
}
Pour les strings récursives : le cas de base c'est presque toujours *s == '\0', et le cas récursif avance avec s + 1.
ERREURS FRÉQUENTES — ÉVITE LE GAME OVER
❌ ERREUR — PAS DE CAS DE BASE
int bad_factorial(int n)
{
    /* ❌ PAS DE CAS DE BASE */
    return (n * bad_factorial(n - 1));
    /* → Segfault / stack overflow */
}
✅ CORRECT
int good_factorial(int n)
{
    /* ✅ CAS DE BASE EN PREMIER */
    if (n <= 1)
        return (1);
    return (n * good_factorial(n - 1));
}
❌ ERREUR — PAS DE PROGRESSION
int bad_func(int n)
{
    if (n == 0)
        return (0);
    /* ❌ n ne change pas → infini */
    return (bad_func(n));
}
✅ CORRECT
int good_func(int n)
{
    if (n == 0)
        return (0);
    /* ✅ n - 1 : progression vers 0 */
    return (good_func(n - 1));
}
TIPS SPÉCIAL HOLBERTON
🎓 POUR TES PROJETS
/* Header guard pour tes fonctions récursives */
#ifndef MAIN_H
#define MAIN_H

int  _strlen(char *s);
void _puts(char *str);
int  _strcmp(char *s1, char *s2);
int  factorial(int n);
int  fibonacci(int n);

#endif /* MAIN_H */
RÉCAP — TON CHEAT CODE FINAL
📝 LES 4 QUESTIONS À SE POSER
1

Quel est mon cas de base ?

La condition qui stoppe tout. Souvent n == 0, n == 1, ou *s == '\0'

2

Comment je me rapproche du cas de base ?

n - 1, s + 1, division par 2... L'argument doit toujours diminuer

3

Que retourne l'appel récursif ?

La valeur retournée sert à calculer le résultat du niveau actuel

4

Est-ce que je combine bien les résultats ?

n * func(n-1) pour factorielle, 1 + func(s+1) pour strlen...