0Pricing
Coding Interview Prep · Leçon

Cadre de la récursivité : cas de base, confiance, construction

Appliquez la méthode en trois étapes pour écrire des solutions récursives correctes à la factorielle, à la puissance et à la somme des chiffres sans suivre chaque appel.

Cadre de la récursivité : cas de base, confiance, construction est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.

Pourquoi la récursivité semble difficile

La plupart des débutants essaient de suivre mentalement chaque appel récursif, ce qui devient rapidement accablant, même pour une récursivité de cinq niveaux. L’approche professionnelle consiste à utiliser un cadre en trois étapes — Cas de base, Confiance, Construction — qui vous permet d’écrire des fonctions récursives correctes sans simuler mentalement l’ensemble de l’arbre des appels.

Ce cadre est parfois appelé l’acte de foi : vous faites confiance à votre fonction pour fonctionner sur des entrées plus petites et utilisez cette hypothèse pour construire la solution destinée aux entrées plus grandes.

Étape 1 : Définir le cas de base

Le cas de base est l’entrée la plus simple pour laquelle la réponse est connue sans récursion supplémentaire. Toute fonction récursive doit comporter au moins un cas de base ; sans celui-ci, la fonction récursiverait indéfiniment (débordement de pile). Les bons cas de base sont : une liste vide, un seul élément, n == 0, n == 1, ou un problème qui se réduit à une identité triviale.

Écrivez d’abord le cas de base, avant toute logique récursive. Repérez-le en vous demandant : « Quelle est la plus petite version de ce problème à laquelle je peux répondre immédiatement ? »

# Base cases for common problems
def factorial(n):
    if n == 0:          # base case: 0! = 1
        return 1
    # ... recursive step below

def sum_list(lst):
    if not lst:         # base case: sum of empty list is 0
        return 0
    # ...

def height(node):
    if node is None:    # base case: height of null node is 0
        return 0
    # ...

print('Base cases identified')

Étape 2 : Faire confiance à l’appel récursif

L’étape de confiance est un saut de foi : supposez que votre fonction fonctionne déjà correctement pour toute entrée strictement plus petite que l’entrée actuelle. Vous n’avez pas besoin de le démontrer maintenant pour chaque entrée plus petite — la preuve par récurrence le garantit. Appelez simplement votre fonction sur le sous-problème plus petit et faites-lui confiance pour renvoyer le résultat correct.

C’est l’étape que les débutants sautent, en essayant plutôt de simuler mentalement l’exécution. Résistez à cette envie : une fois que vous avez assimilé ce cadre, il s’adapte à une récursion d’une profondeur arbitraire.

# Trust example: sum_list([3, 1, 4, 1, 5])
# Trust: sum_list([1, 4, 1, 5]) = 11  (we TRUST this, don't trace it)
# Build: 3 + 11 = 14

# So:
def sum_list(lst):
    if not lst:
        return 0
    # Trust that sum_list(lst[1:]) returns sum of the rest
    return lst[0] + sum_list(lst[1:])

print(sum_list([3, 1, 4, 1, 5]))  # 14

Étape 3 : Construire la solution

L’étape de construction combine le résultat du sous-problème, auquel vous faites confiance, avec la contribution de l’élément actuel afin de produire la réponse pour l’entrée complète. Il s’agit généralement d’une seule ligne : appliquer une opération à l’élément actuel et au résultat de l’appel récursif. Exemples courants : ajouter à une somme, ajouter au début d’une liste, incrémenter un compteur, combiner deux sous-résultats.

def factorial(n):
    if n == 0:
        return 1
    # Trust: factorial(n-1) gives (n-1)!
    # Build: n * (n-1)! = n!
    return n * factorial(n - 1)

def power(base, exp):
    if exp == 0:
        return 1
    # Trust: power(base, exp-1) gives base^(exp-1)
    # Build: base * base^(exp-1) = base^exp
    return base * power(base, exp - 1)

print(factorial(6))    # 720
print(power(2, 10))    # 1024

Appliquer le cadre à la somme des chiffres

Problème : calculer la somme des chiffres d’un entier non négatif. Cas de base : n == 0 → la somme vaut 0 (ou n < 10 → n lui-même). Confiance : sumDigits(n // 10) renvoie la somme de tous les chiffres sauf le dernier. Construction : ajouter le dernier chiffre n % 10 au résultat obtenu par l’appel récursif. Le cadre fournit la solution en trois étapes déclaratives.

def sumDigits(n):
    if n < 10:
        return n            # base case: single digit
    # Trust: sumDigits(n // 10) gives sum of all digits except last
    # Build: add the last digit
    return n % 10 + sumDigits(n // 10)

print(sumDigits(0))      # 0
print(sumDigits(7))      # 7
print(sumDigits(123))    # 6
print(sumDigits(9999))   # 36

Fibonacci : deux sous-problèmes

Fibonacci nécessite deux appels récursifs : fib(n-1) et fib(n-2). Appliquez le cadre : les cas de base sont fib(0) = 0 et fib(1) = 1. Confiance : les deux appels sur des entrées plus petites renvoient les valeurs correctes de Fibonacci. Construction : renvoyer leur somme. Cette implémentation naïve est en O(2^n) — nous corrigerons cela dans la leçon sur la mémoïsation.

def fib(n):
    if n <= 1:
        return n      # base cases: fib(0)=0, fib(1)=1
    # Trust both smaller sub-problems
    return fib(n - 1) + fib(n - 2)

for i in range(8):
    print(f'fib({i}) = {fib(i)}')  # 0,1,1,2,3,5,8,13

Inverser une chaîne récursivement

Problème : inverser une chaîne récursivement. Cas de base : chaîne vide ou caractère unique — elle est déjà inversée. Confiance : reverse(s[1:]) renvoie l’inverse de tout ce qui suit le premier caractère. Construction : utiliser append pour placer le premier caractère à la fin du suffixe inversé. Le cadre fournit une solution en trois lignes.

def reverse_str(s):
    if len(s) <= 1:
        return s            # base case
    # Trust: reverse_str(s[1:]) = reverse of 'ello' for 'hello'
    # Build: append first character at end
    return reverse_str(s[1:]) + s[0]

print(reverse_str(''))        # ''
print(reverse_str('a'))       # 'a'
print(reverse_str('hello'))   # 'olleh'
print(reverse_str('racecar')) # 'racecar'

Compter des occurrences récursivement

Problème : compter récursivement les occurrences d’une valeur cible dans une liste. Cas de base : liste vide — le compte vaut 0. Confiance : count(lst[1:], target) renvoie le nombre d’occurrences dans le reste de la liste. Construction : ajouter 1 si le premier élément correspond à la cible, sinon ajouter 0. Chaque étape récursive progresse vers le cas de base en réduisant la taille de la liste de 1.

def count_occurrences(lst, target):
    if not lst:
        return 0
    # Trust: count in rest of list is handled recursively
    # Build: add 1 if first element matches, else 0
    return (1 if lst[0] == target else 0) + count_occurrences(lst[1:], target)

print(count_occurrences([1, 2, 3, 2, 4, 2], 2))  # 3
print(count_occurrences([], 5))                    # 0
print(count_occurrences([7, 7, 7], 7))             # 3

Vérifier si une liste est triée

Problème : vérifier récursivement si une liste est triée dans l’ordre croissant. Cas de base : une liste de 0 ou 1 élément est toujours triée. Confiance : is_sorted(lst[1:]) indique si le reste de la liste est trié. Construction : la liste est triée si le premier élément est <= au deuxième AND si le reste de la liste est trié. C’est un exemple clair où l’étape de construction utilise un AND logique entre deux conditions.

def is_sorted(lst):
    if len(lst) <= 1:
        return True
    # Trust: is_sorted(lst[1:]) tells us if tail is sorted
    # Build: head <= second element AND tail is sorted
    return lst[0] <= lst[1] and is_sorted(lst[1:])

print(is_sorted([]))           # True
print(is_sorted([1]))          # True
print(is_sorted([1, 2, 3, 4])) # True
print(is_sorted([1, 3, 2, 4])) # False

Recherche binaire récursive (réexaminée)

Recherche binaire exprimée récursivement avec le cadre : cas de base : lo > hi → élément introuvable (renvoyer -1). Confiance : l’appel récursif sur la moitié appropriée trouve la cible ou renvoie -1. Construction : calculer mid, comparer, puis appeler la moitié appropriée. La forme récursive montre clairement la structure diviser pour régner, même si la forme itérative est préférable en production pour utiliser un espace en O(1).

def binary_search(arr, target, lo, hi):
    if lo > hi:          # base case: search space exhausted
        return -1
    mid = lo + (hi - lo) // 2
    if arr[mid] == target:
        return mid
    # Trust both halves return correct results
    if arr[mid] < target:
        return binary_search(arr, target, mid + 1, hi)
    else:
        return binary_search(arr, target, lo, mid - 1)

arr = [1, 3, 5, 7, 9, 11]
print(binary_search(arr, 7, 0, len(arr) - 1))   # 3
print(binary_search(arr, 4, 0, len(arr) - 1))   # -1

Quand utiliser la récursion plutôt que l’itération

La récursion est particulièrement efficace lorsque le problème se décompose naturellement en sous-problèmes plus petits du même type (arbres, diviser pour régner, retour sur trace). L’itération est préférable lorsque : la profondeur de récursion est importante (ce qui risque de provoquer un débordement de pile en Python, dont la valeur par défaut est d’environ 1 000), les versions récursive et itérative sont tout aussi claires, ou le problème consiste en une simple boucle (factorial, Fibonacci sans mémoïsation).

Une bonne règle générale : si dessiner un arbre de récursion vous semble naturel, utilisez la récursion. Si l’arbre est une ligne droite (récursion terminale), convertissez-la en itération.

import sys

# Python's default recursion limit
print('Recursion limit:', sys.getrecursionlimit())  # 1000

# A list of 2000 elements would overflow the recursive sum_list
# Use iteration for safety:
def sum_list_iter(lst):
    total = 0
    for x in lst:
        total += x
    return total

big = list(range(2000))
print(sum_list_iter(big))  # 1999000 — no stack overflow

Vérification rapide

Évaluez votre compréhension des concepts de structures de données et d’algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.

Récapitulatif de la leçon

Dans cette leçon, vous avez appris que le cadre en trois étapes est le Cas de base (réponse connue la plus simple), la Confiance (supposer que le sous-problème est résolu) et la Construction (combiner l’élément actuel avec le résultat obtenu par confiance), qu’il faut écrire d’abord les cas de base et éviter de retracer mentalement des arbres d’appels complets, et qu’il faut utiliser l’itération lorsque la profondeur de récursion risque de provoquer un débordement de pile ou lorsque les formes récursive et itérative sont tout aussi claires. Nous allons maintenant visualiser la pile d’appels en détail.

Questions Fréquemment Posées

La leçon « Cadre de la récursivité : cas de base, confiance, construction » est-elle gratuite ?

Oui — le texte complet de « Cadre de la récursivité : cas de base, confiance, construction » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Cadre de la récursivité : cas de base, confiance, construction » ?

Appliquez la méthode en trois étapes pour écrire des solutions récursives correctes à la factorielle, à la puissance et à la somme des chiffres sans suivre chaque appel. Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?

Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.

Combien de temps prend la leçon « Cadre de la récursivité : cas de base, confiance, construction » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?

Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

  1. Cadre de la récursivité : cas de base, confiance, construction
  2. Visualiser la pile d’appels
  3. Compromis entre récursivité et itération
  4. Mémoïsation : mettre en cache les résultats récursifs
← Retour à Coding Interview Prep