Compromis entre récursivité et itération
Convertissez la factorielle et Fibonacci récursifs en boucles itératives et expliquez quand la limite de récursivité et la taille de pile de Python rendent l’itération préférable.
Compromis entre récursivité et itération 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.
La dualité récursive-itérative
Tout algorithme qui peut être écrit récursivement peut aussi être écrit de manière itérative, et inversement. La version récursive reflète souvent plus fidèlement la définition mathématique du problème, tandis que la version itérative vous donne un contrôle explicite de la mémoire et évite les risques de débordement de pile. Le choix entre les deux est une décision pragmatique fondée sur la lisibilité, les limites de profondeur et les exigences de performance.
Lors d’un entretien, être capable de présenter les deux versions et d’expliquer les compromis constitue un signe fort de maîtrise.
Factorielle : récursive ou itérative
La factorielle est l’exemple classique. La version récursive encode directement la définition mathématique n! = n × (n-1)!. Elle utilise un espace de pile en O(n), en raison des n valeurs de retour en attente. La version itérative parcourt les valeurs de 1 à n dans une boucle et utilise un espace en O(1). Pour n = 1000, la version récursive atteint la limite par défaut de Python ; la version itérative gère des valeurs de n arbitrairement grandes.
def factorial_rec(n):
if n == 0:
return 1
return n * factorial_rec(n - 1) # O(n) stack
def factorial_iter(n):
result = 1
for i in range(2, n + 1):
result *= i # O(1) stack
return result
print(factorial_rec(10)) # 3628800
print(factorial_iter(10)) # 3628800
# Large n: iterative works, recursive may overflow
print(factorial_iter(1000) > 0) # True (Python handles big ints)Fibonacci : exponentielle ou linéaire
La version récursive naïve de Fibonacci a une complexité temporelle en O(2^n) — elle est désastreusement lente pour les grandes valeurs de n. La version itérative a une complexité temporelle en O(n) et une complexité spatiale en O(1). La récursion mémoïsée (dans la prochaine leçon) a également une complexité temporelle en O(n), mais une complexité spatiale en O(n) à cause du dictionnaire de mémoïsation et de la pile de profondeur O(n). Pour Fibonacci, l’approche itérative est optimale selon tous les critères. Pour n = 50, la récursion naïve prend des secondes, tandis que l’itération prend des microsecondes.
import time
def fib_rec(n):
if n <= 1: return n
return fib_rec(n-1) + fib_rec(n-2) # O(2^n)
def fib_iter(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a # O(n) time, O(1) space
# Timing comparison for n=35
start = time.time()
fib_rec(35)
print(f'Recursive n=35: {time.time()-start:.3f}s')
start = time.time()
fib_iter(35)
print(f'Iterative n=35: {time.time()-start:.6f}s')
print(fib_iter(100)) # handles large nParcours d’arbre : récursif ou itératif
Le parcours récursif d’un arbre est naturellement élégant, car la structure de l’arbre reflète la récursion. Cependant, pour un arbre fortement déséquilibré (qui ressemble essentiellement à une liste chaînée), la profondeur de récursion est égale à la hauteur de l’arbre = O(n), ce qui risque de provoquer un débordement de pile. La version itérative utilisant une pile explicite n’a pas de limite de profondeur et permet à la taille de la pile d’augmenter dans le tas plutôt que dans la pile d’appels.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val; self.left = left; self.right = right
def preorder_rec(root, result=None):
if result is None: result = []
if root:
result.append(root.val)
preorder_rec(root.left, result)
preorder_rec(root.right, result)
return result
def preorder_iter(root):
if not root: return []
result, stack = [], [root]
while stack:
node = stack.pop()
result.append(node.val)
if node.right: stack.append(node.right)
if node.left: stack.append(node.left)
return result
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(preorder_rec(root)) # [1, 2, 4, 5, 3]
print(preorder_iter(root)) # [1, 2, 4, 5, 3]Tri fusion : récursif ou itératif (ascendant)
Le tri fusion est naturellement récursif (diviser, récursivement traiter, fusionner). Le tri fusion itératif ascendant évite entièrement la récursion : commencez par des sous-tableaux de taille 1, fusionnez les paires adjacentes en sous-tableaux de taille 2, puis de taille 4, et ainsi de suite, en doublant la taille des sous-tableaux à chaque passe. Le tri fusion ascendant s’exécute en O(n log n), utilise O(n) d’espace (pour le tampon de fusion) et O(1) d’espace de pile.
def merge_sort_iterative(arr):
n = len(arr)
size = 1
while size < n:
for start in range(0, n, 2 * size):
mid = min(start + size, n)
end = min(start + 2 * size, n)
left = arr[start:mid]
right = arr[mid:end]
# Merge
i = j = 0
for k in range(start, end):
if i < len(left) and (j >= len(right) or left[i] <= right[j]):
arr[k] = left[i]; i += 1
else:
arr[k] = right[j]; j += 1
size *= 2
return arr
print(merge_sort_iterative([5, 2, 4, 6, 1, 3])) # [1,2,3,4,5,6]Quand la récursion est clairement préférable
La récursion est particulièrement adaptée lorsque le problème présente une structure arborescente qui se transpose directement dans le graphe des appels, lorsque les cas de base sont naturels et lorsque la profondeur est bornée (O(log n) pour les arbres équilibrés et les algorithmes diviser pour régner). Exemples : analyse de JSON, parcours de répertoires, arbres de jeu et problèmes de retour sur trace. Dans ces cas, le code récursif est plus court, plus clair et plus facile à démontrer correct que la version itérative équivalente.
# Recursion is clearest for JSON-like nested structures
def flatten(nested):
result = []
for item in nested:
if isinstance(item, list):
result.extend(flatten(item)) # recurse on sub-list
else:
result.append(item)
return result
print(flatten([1, [2, [3, 4], 5], 6])) # [1, 2, 3, 4, 5, 6]
print(flatten([])) # []
print(flatten([[1, [2]], [3, [4, [5]]]])) # [1, 2, 3, 4, 5]Quand l’itération est clairement préférable
L’itération est le bon choix lorsque : la profondeur est O(n) et que n est grand (plus d’environ 500 dans un code Python sûr), lorsque les versions récursive et itérative sont aussi lisibles l’une que l’autre (Fibonacci, factorielle), ou lorsque le problème est fondamentalement séquentiel et ne présente aucune décomposition naturelle en sous-problèmes. Les boucles simples qui parcourent des tableaux de gauche à droite — sommes cumulées, fenêtres glissantes, deux pointeurs — doivent toujours être écrites de manière itérative.
# Iterative is clearest for sequential array processing
def running_max(nums):
result = []
curr_max = float('-inf')
for n in nums:
curr_max = max(curr_max, n)
result.append(curr_max)
return result
print(running_max([3, 1, 4, 1, 5, 9, 2, 6])) # [3,3,4,4,5,9,9,9]
# No natural recursion here — iteration is the only sensible choiceConvertir une récursion DFS en itération
Voici une approche systématique : toute recherche DFS récursive devient itérative en empilant les arguments récursifs dans une pile explicite. L’idée essentielle est que l’appel récursif f(args) équivaut à empiler args puis à exécuter une boucle. Pour un traitement en postordre (lorsque vous avez besoin des résultats des enfants avant celui du parent), vous devrez peut-être utiliser une approche en deux passes ou un indicateur de visite.
# Post-order iterative using two stacks
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val=val; self.left=left; self.right=right
def postorder_iter(root):
if not root: return []
s1, s2 = [root], []
while s1:
node = s1.pop()
s2.append(node.val)
if node.left: s1.append(node.left)
if node.right: s1.append(node.right)
return s2[::-1] # reverse gives post-order
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(postorder_iter(root)) # [4, 5, 2, 3, 1]Surcharge liée à la récursion
Chaque appel récursif en Python entraîne une surcharge non négligeable : une nouvelle trame est créée (ce qui alloue de la mémoire dans le tas), les variables locales sont initialisées et un pointeur vers l’adresse de retour est enregistré. Les mesures montrent que la surcharge d’un appel de fonction en Python est d’environ 100 à 200 nanosecondes par appel. Pour une profondeur de récursion de 10^6, cela représente 0,1 à 0,2 seconde de surcharge pure, indépendamment du travail de l’algorithme. Les boucles itératives évitent entièrement cette surcharge.
import time
def rec_sum(n):
if n == 0: return 0
return n + rec_sum(n - 1)
def iter_sum(n):
total = 0
for i in range(n + 1):
total += i
return total
import sys; sys.setrecursionlimit(10000)
n = 5000
start = time.time()
for _ in range(100): rec_sum(n)
print(f'Recursive sum({n}) x100: {(time.time()-start)*1000:.2f}ms')
start = time.time()
for _ in range(100): iter_sum(n)
print(f'Iterative sum({n}) x100: {(time.time()-start)*1000:.2f}ms')Décider lors d’un entretien
Lors d’un entretien de programmation, si vous avez le choix, demandez-vous : « La profondeur de récursion est-elle bornée par O(log n) ? » Si oui, la récursion convient. « La profondeur de récursion est-elle O(n) ? » — préférez l’itération ou précisez que vous convertiriez la solution en version itérative pour le code de production. « Le problème a-t-il naturellement une structure arborescente ou diviser pour régner ? » — privilégiez la récursion. « Le problème consiste-t-il en un parcours séquentiel ? » — utilisez l’itération.
Indiquez toujours votre raisonnement : « J’utiliserai la récursion ici, car la profondeur est O(log n) pour un BST équilibré ; l’espace de pile O(log n) est donc acceptable. »
Récapitulatif : tableau des compromis
Pour résumer les compromis : le code récursif est souvent plus court et reflète la structure du problème, mais il coûte O(profondeur) d’espace de pile et entraîne une surcharge liée aux appels de fonction. Le code itératif est plus long, mais il utilise O(1) d’espace de pile et évite les limites de la récursion. La récursion mémoïsée (dans la prochaine leçon) constitue un compromis : elle conserve la clarté de la récursion tout en éliminant les recalculs redondants. Précisez toujours la complexité spatiale, y compris l’espace utilisé par la pile d’appels, lorsque vous analysez votre solution.
rows = [
('Factorial', 'O(n) / O(1)', 'O(n) / O(1)', 'Same time; iter wins on space'),
('Fibonacci', 'O(2^n) / O(n)', 'O(n) / O(1)', 'Iter massively wins'),
('Binary search','O(log n) / O(log n)', 'O(log n) / O(1)', 'Iter wins on space'),
('Tree DFS', 'O(n) / O(h)', 'O(n) / O(h)', 'Equal; rec cleaner'),
('Merge sort', 'O(n log n) / O(log n)', 'O(n log n) / O(1)', 'BU-iter wins on stack'),
]
for name, rec, it, note in rows:
print(f'{name:<15} rec={rec:<22} iter={it:<22} {note}')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 : la récursion est préférable lorsque la profondeur est O(log n) ou que le problème a naturellement une structure arborescente, tandis que l’itération est préférable lorsque la profondeur est O(n) ou que le problème est séquentiel ; la version récursive naïve de Fibonacci est en O(2^n), tandis que la version itérative s’exécute en O(n) et utilise O(1) d’espace ; et toute recherche DFS récursive peut être convertie en version itérative en gérant une pile explicite dans le tas. Dans la prochaine leçon, vous appliquerez la mémoïsation pour éliminer les appels récursifs redondants.
Questions Fréquemment Posées
La leçon « Compromis entre récursivité et itération » est-elle gratuite ?
Oui — le texte complet de « Compromis entre récursivité et itération » 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 « Compromis entre récursivité et itération » ?
Convertissez la factorielle et Fibonacci récursifs en boucles itératives et expliquez quand la limite de récursivité et la taille de pile de Python rendent l’itération préférable. 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 « Compromis entre récursivité et itération » ?
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
- Cadre de la récursivité : cas de base, confiance, construction
- Visualiser la pile d’appels
- Compromis entre récursivité et itération
- Mémoïsation : mettre en cache les résultats récursifs