Récursivité et méthode de l’arbre de récursion
Suivez les appels récursifs dans des arbres, appliquez le théorème maître et déduisez les complexités temporelles du tri fusion, de la factorielle et des variantes de Fibonacci.
Récursivité et méthode de l’arbre de récursion est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 3 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.
Récursivité et pile d’appels
Lorsqu’une fonction s’appelle elle-même, chaque appel ajoute une trame de pile, qui s’accumule jusqu’à l’atteinte d’un cas de base, puis les appels se dépilent. Visualiser ce mécanisme est la première étape pour analyser la récursivité.
def factorial(n):
if n == 0: # base case
return 1
return n * factorial(n - 1) # recursive call
# Call chain: factorial(4)
# 4 * factorial(3)
# 3 * factorial(2)
# 2 * factorial(1)
# 1 * factorial(0) -> 1
# Unwinds: 1, 2, 6, 24
print(factorial(5)) # 120L’arbre de récursivité de Fibonacci
Un arbre de récursivité développe chaque appel en ses sous-appels. La version naïve de Fibonacci se divise en deux appels à chaque fois, formant un arbre d’environ 2^n nœuds : cela donne O(2^n). Consultez le code.
call_count = [0]
def fib_naive(n):
call_count[0] += 1
if n <= 1:
return n
return fib_naive(n-1) + fib_naive(n-2)
for n in [5, 10, 15, 20]:
call_count[0] = 0
result = fib_naive(n)
print(f'fib({n})={result}, calls={call_count[0]}')
# Calls roughly double each time n increases by 1Identifier les sous-problèmes répétitifs
Dans cet arbre, les mêmes appels, comme fib(3), se répètent sur différentes branches. Ces sous-problèmes qui se chevauchent indiquent qu’il faut utiliser la mémoïsation, qui réduit O(2^n) à O(n).
# Memoised: each unique sub-problem computed once
def fib_memo(n, memo={}):
if n in memo: return memo[n]
if n <= 1: return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]
call_count2 = [0]
def fib_counted(n, memo={}):
call_count2[0] += 1
if n in memo: return memo[n]
if n <= 1: return n
memo[n] = fib_counted(n-1, memo) + fib_counted(n-2, memo)
return memo[n]
fib_counted(20)
print(f'calls with memo: {call_count2[0]}') # only 21Arbre de récursivité du tri fusion
L’arbre du tri fusion comporte log n niveaux, et chaque niveau effectue au total O(n) opérations : chaque élément est traité une fois. En les multipliant, on obtient O(n log n). Consultez le code.
# Merge sort: at each level, n total elements are merged
# Level 0: 1 merge of n elements -> n work
# Level 1: 2 merges of n/2 each -> n work
# Level 2: 4 merges of n/4 each -> n work
# ...log(n) levels...
# Total: n * log(n)
# Verify with operation counter:
def merge_sort_counted(arr):
ops = [0]
def _sort(a):
if len(a) <= 1: return a
m = len(a) // 2
l, r = _sort(a[:m]), _sort(a[m:])
result, i, j = [], 0, 0
while i < len(l) and j < len(r):
ops[0] += 1
if l[i] <= r[j]: result.append(l[i]); i+=1
else: result.append(r[j]); j+=1
return result + l[i:] + r[j:]
return _sort(arr), ops[0]
_, c = merge_sort_counted(list(range(64, 0, -1)))
print(f'Merge ops: {c}') # ~384 ~ 64*log2(64)=384Le théorème maître
Le théorème maître résout T(n) = a*T(n/b) + O(n^d) selon trois cas. Pour le tri fusion (a=2, b=2, d=1), il donne O(n log n). Mémorisez les trois cas pour l’examen.
# Merge sort: T(n) = 2*T(n/2) + O(n)
# a=2, b=2, d=1, log_b(a)=log2(2)=1=d => O(n log n)
# Binary search: T(n) = 1*T(n/2) + O(1)
# a=1, b=2, d=0, log2(1)=0=d => O(log n)
# Strassen matrix mult: T(n) = 7*T(n/2) + O(n^2)
# a=7, b=2, d=2, log2(7)~2.81 > 2 => O(n^log2(7)) ~ O(n^2.81)
import math
print('log2(7) =', math.log2(7)) # 2.807...Dessiner des arbres de récursivité, étape par étape
Pour dessiner un arbre de récursivité : placez T(n) en haut, développez chaque appel, additionnez le travail effectué à chaque niveau, puis multipliez par le nombre de niveaux. Entraînez-vous jusqu’à ce que cela devienne automatique.
# Factorial: T(n) = T(n-1) + O(1)
# Tree is a chain: n levels, O(1) each -> O(n)
# Fibonacci: T(n) = T(n-1) + T(n-2) + O(1)
# Binary tree of depth n, ~2^n nodes -> O(2^n)
# Merge sort: T(n) = 2*T(n/2) + O(n)
# Log levels, n work each -> O(n log n)
def count_recursive_calls(n, results=[]):
if n <= 1:
results.append(n)
return n
return count_recursive_calls(n-1, results) + count_recursive_calls(n-2, results)
results = []
count_recursive_calls(8, results)
print(f'fib(8) leaf calls: {len(results)}')Récursivité exponentielle : sous-ensembles
Générer tous les sous-ensembles prend O(2^n) — il y en a exactement 2^n, vous ne pouvez donc pas faire mieux. Chaque élément est inclus ou exclu, ce qui forme un arbre binaire de choix. Consultez le code.
def subsets(nums):
result = []
def backtrack(start, current):
result.append(list(current)) # O(n) copy
for i in range(start, len(nums)):
current.append(nums[i])
backtrack(i + 1, current)
current.pop()
backtrack(0, [])
return result
nums = [1, 2, 3]
ss = subsets(nums)
print(len(ss)) # 8 = 2^3
print(ss)Récursivité terminale et optimisation
La récursivité terminale se produit lorsque l’appel récursif constitue la toute dernière étape. Certains langages réutilisent alors la trame, mais Python ne le fait pas : les appels profonds débordent donc toujours. Utilisez plutôt une boucle.
# Tail-recursive factorial (accumulator pattern)
def fact_tail(n, acc=1):
if n == 0:
return acc
return fact_tail(n - 1, n * acc) # tail call
# Python does NOT TCO, so this overflows for large n
# Instead, convert to iterative:
def fact_iter(n):
acc = 1
while n > 0:
acc *= n
n -= 1
return acc
print(fact_tail(10)) # 3628800
print(fact_iter(10)) # 3628800Complexité spatiale de la récursivité
Chaque appel récursif conserve une trame, la récursivité consomme donc un espace en O(profondeur). Une récursivité linéaire est en O(n) ; un parcours en profondeur d’un arbre équilibré est en O(log n). Allez trop profondément et vous atteindrez RecursionError.
import sys
print(sys.getrecursionlimit()) # default 1000
# Increase limit for deep problems
sys.setrecursionlimit(10000)
# Track max depth manually
def max_depth_tracker(n, depth=0, max_seen=[0]):
max_seen[0] = max(max_seen[0], depth)
if n <= 0:
return
max_depth_tracker(n - 1, depth + 1, max_seen)
return max_seen[0]
print(max_depth_tracker(50)) # 50 => O(n) stack framesArbre de récursivité du tri rapide
Le tri rapide est en O(n log n) avec un bon pivot, mais un mauvais pivot sur une entrée déjà triée le dégrade en O(n^2). C’est pourquoi il est important de choisir le pivot aléatoirement. Consultez le code.
import random
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = random.choice(arr) # randomised -> O(n log n) expected
less = [x for x in arr if x < pivot]
equal = [x for x in arr if x == pivot]
greater = [x for x in arr if x > pivot]
return quick_sort(less) + equal + quick_sort(greater)
print(quick_sort([3, 6, 8, 10, 1, 2, 1])) # sortedFonction puissance : récursivité en log n
La méthode naïve x^n nécessite O(n) multiplications, mais l’élévation au carré divise le travail par deux à chaque étape : x^n = (x^(n/2))^2. On obtient ainsi un élégant O(log n) : la réduction de moitié en action. Consultez le code.
def fast_pow(x, n):
if n == 0: return 1
if n < 0: return 1 / fast_pow(x, -n)
if n % 2 == 0:
half = fast_pow(x, n // 2)
return half * half # O(log n) calls
return x * fast_pow(x, n - 1)
print(fast_pow(2, 10)) # 1024
print(fast_pow(3, 5)) # 243
# Only log2(10)=3-4 recursive calls for n=10Vérification rapide
Vérification rapide — montrez ce que la méthode des arbres de récursivité vous a appris. Une question, prenez votre temps. 🌳
Récapitulatif de la leçon
Récapitulatif : un arbre de récursivité révèle le travail total, le théorème maître résout les récurrences diviser pour régner, et la récursivité consomme un espace de pile en O(profondeur).
Questions Fréquemment Posées
La leçon « Récursivité et méthode de l’arbre de récursion » est-elle gratuite ?
Oui — le texte complet de « Récursivité et méthode de l’arbre de récursion » 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 « Récursivité et méthode de l’arbre de récursion » ?
Suivez les appels récursifs dans des arbres, appliquez le théorème maître et déduisez les complexités temporelles du tri fusion, de la factorielle et des variantes de Fibonacci. 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 3 sur 4.
Combien de temps prend la leçon « Récursivité et méthode de l’arbre de récursion » ?
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
- La notation grand O depuis le début
- Analyser les boucles et les boucles imbriquées
- Récursivité et méthode de l’arbre de récursion
- Complexité spatiale et compromis