Visualizzare lo stack delle chiamate
Usi il modulo sys di Python e il tracing con print per osservare la crescita e la riduzione degli stack frame e comprendere i rischi di stack overflow nella ricorsione profonda
Visualizzare lo stack delle chiamate è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Che cos'è lo stack delle chiamate?
Ogni chiamata di funzione in Python crea un frame dello stack nello stack delle chiamate. Il frame memorizza le variabili locali della funzione, il suo indirizzo di ritorno (il punto in cui l'esecuzione riprende dopo la restituzione della funzione) e il puntatore all'istruzione corrente. Quando una funzione restituisce un risultato, il suo frame viene rimosso e il controllo torna al chiamante. Lo stack delle chiamate cresce verso il basso a ogni chiamata e si riduce a ogni restituzione.
Comprendere lo stack delle chiamate è essenziale per eseguire il debug del codice ricorsivo, stimare l'uso della memoria ed evitare errori di overflow dello stack nelle ricorsioni profonde.
import traceback
def outer():
inner()
def inner():
# Print the current call stack
traceback.print_stack()
outer()
# Shows: module -> outer -> innerOsservare i frame dello stack con sys
Il modulo Python sys fornisce strumenti per esaminare lo stack delle chiamate durante l'esecuzione. sys._getframe(n) restituisce il frame dello stack che si trova n livelli sopra la funzione corrente. Ogni frame contiene un dizionario f_locals con le variabili locali e f_code.co_name per il nome della funzione. Inserire stampe di debug all'interno di una funzione ricorsiva mostra come i frame si accumulano e si dissolvono.
import sys
def countdown(n):
depth = 0
frame = sys._getframe(0)
while frame:
depth += 1
frame = frame.f_back
print(' ' * (n * 2) + f'countdown({n}) called, stack depth={depth}')
if n <= 0:
return
countdown(n - 1)
print(' ' * (n * 2) + f'countdown({n}) returning')
countdown(3)Tracciare factorial nello stack delle chiamate
Tracci factorial(4) nello stack delle chiamate. Le chiamate si accumulano: factorial(4) chiama factorial(3), che chiama factorial(2), che chiama factorial(1), che chiama factorial(0). Al caso base, lo stack contiene 5 frame. Le restituzioni si svolgono a ritroso: factorial(0) restituisce 1; factorial(1) restituisce 1×1=1; factorial(2) restituisce 2×1=2; factorial(3) restituisce 3×2=6; factorial(4) restituisce 4×6=24. La profondità è uguale a n+1 e la complessità spaziale è O(n).
def factorial(n, indent=0):
prefix = ' ' * indent
print(prefix + f'-> factorial({n})')
if n == 0:
print(prefix + '<- returns 1')
return 1
result = n * factorial(n - 1, indent + 1)
print(prefix + f'<- returns {result}')
return result
factorial(4)Stack overflow: il limite di ricorsione di Python
Python solleva RecursionError quando lo stack delle chiamate supera il proprio limite (per impostazione predefinita, circa 1000 frame). Questo protegge dal rischio che una ricorsione infinita consumi tutta la memoria. Per problemi con dimensione dell'input n = 10^4 o superiore, una soluzione ricorsiva con profondità O(n) andrà in errore senza aumentare il limite. L'equivalente iterativo usa spazio O(1) nello stack, perché utilizza un solo frame per la funzione contenitore.
import sys
print('Recursion limit:', sys.getrecursionlimit())
def deep_recursion(n):
if n == 0:
return 0
return 1 + deep_recursion(n - 1)
# Safe: within limit
try:
print(deep_recursion(900))
except RecursionError:
print('Overflow at 900')
# Overflow
try:
print(deep_recursion(2000))
except RecursionError:
print('RecursionError at 2000 — limit exceeded!')Aumentare il limite di ricorsione
È possibile aumentare il limite di ricorsione di Python con sys.setrecursionlimit(n), ma si tratta di una soluzione tampone. Il limite predefinito esiste perché ogni frame dello stack occupa memoria (in genere diverse centinaia di byte su CPython). Impostare il limite a 10^6 e poi chiamare una ricorsione profonda 10^5 può allocare centinaia di megabyte di spazio nello stack. La soluzione corretta consiste di solito nel convertire il codice in una soluzione iterativa o nell'usare la memoizzazione per ridurre la profondità.
import sys
# Only increase when you are certain of the maximum depth
# and have confirmed it is safe
original = sys.getrecursionlimit()
sys.setrecursionlimit(5000)
def sum_to(n):
if n == 0:
return 0
return n + sum_to(n - 1)
print(sum_to(3000)) # Works with increased limit
sys.setrecursionlimit(original) # restore
print('Limit restored:', sys.getrecursionlimit())Lo stack delle chiamate nella ricorsione reciproca
La ricorsione reciproca si verifica quando la funzione A chiama la funzione B e la funzione B chiama la funzione A. Lo stack delle chiamate alterna i frame di A e B. Questo schema compare nella determinazione della parità di un numero e nelle simulazioni di macchine a stati. È corretto finché la profondità dello stack rimane limitata, ma può essere più difficile ragionare sulla profondità rispetto a una semplice ricorsione lineare.
def is_even(n):
if n == 0:
return True
return is_odd(n - 1)
def is_odd(n):
if n == 0:
return False
return is_even(n - 1)
# Stack alternates: is_even(4)->is_odd(3)->is_even(2)->is_odd(1)->is_even(0)
print(is_even(4)) # True
print(is_odd(5)) # True
print(is_even(7)) # FalseChiamate terminali e perché Python non le ottimizza
Una chiamata terminale è una chiamata ricorsiva che costituisce l'ultima operazione prima della restituzione: dopo di essa non viene eseguito alcun calcolo. In linguaggi come Haskell o Scheme, le chiamate terminali vengono ottimizzate trasformandole in cicli (ottimizzazione delle chiamate terminali, TCO), ottenendo spazio O(1) nello stack. Python non implementa deliberatamente la TCO. Come ha spiegato Guido van Rossum, preservare l'intera traccia dello stack per il debug era più importante del risparmio di spazio. Perciò, in Python, il codice con ricorsione terminale usa comunque spazio O(n) nello stack.
# Tail-recursive factorial (accumulator pattern)
def factorial_tail(n, acc=1):
if n == 0:
return acc
return factorial_tail(n - 1, acc * n) # tail call
# In Python, this still uses O(n) stack space (no TCO)
# But it IS semantically tail-recursive
print(factorial_tail(6)) # 720
print(factorial_tail(10)) # 3628800
# Iterative version: same logic, O(1) stack
def factorial_iter(n):
acc = 1
while n > 0:
acc *= n
n -= 1
return acc
print(factorial_iter(10)) # 3628800Stampare gli alberi di ricorsione
Visualizzare l'albero di ricorsione aiuta a individuare i sottoproblemi duplicati, che sono l'obiettivo della memoizzazione. Un modo semplice per stampare l'albero consiste nell'aggiungere un parametro indent che aumenta di 2 spazi a ogni livello. Ogni chiamata stampa i propri argomenti all'ingresso e il valore restituito all'uscita. Eseguendo questa procedura per Fibonacci(5) si osservano chiaramente la ramificazione esponenziale e le chiamate ripetute.
def fib_traced(n, indent=0):
prefix = ' ' * indent
print(prefix + f'fib({n})')
if n <= 1:
print(prefix + f'=> {n}')
return n
result = fib_traced(n-1, indent+1) + fib_traced(n-2, indent+1)
print(prefix + f'=> {result}')
return result
fib_traced(4)
# Shows the branching tree with duplicated sub-problemsProfondità dello stack = complessità spaziale
Per qualsiasi funzione ricorsiva, la profondità massima dello stack delle chiamate coincide con la massima profondità della ricorsione raggiunta in un punto qualsiasi dell'esecuzione. Questa profondità corrisponde direttamente alla complessità dello spazio ausiliario. Per la ricorsione lineare (factorial, Fibonacci, inversione di stringhe), la profondità è O(n). Per gli algoritmi divide et impera (merge sort, ricerca binaria), la profondità è O(log n). Per le visite di alberi, la profondità è O(h), dove h è l'altezza dell'albero (O(log n) per alberi bilanciati, O(n) nel caso peggiore).
# Recursion depth = space complexity
# Linear recursion: O(n) stack
def linear_depth(n):
if n == 0: return 0
return 1 + linear_depth(n - 1) # depth = n
# Logarithmic recursion: O(log n) stack
def log_depth(n):
if n <= 1: return 0
return 1 + log_depth(n // 2) # depth = log2(n)
print('n=32 linear depth:', 32)
print('n=32 log depth:', log_depth(32)) # 5
print('n=1024 log depth:', log_depth(1024)) # 10Convertire la ricorsione in iterazione con uno stack esplicito
Qualsiasi algoritmo ricorsivo può essere reso iterativo gestendo esplicitamente lo stack delle chiamate con una lista Python. Invece di lasciare che il sistema operativo gestisca i frame, si inseriscono «attività» nella lista e le si estraggono in un ciclo. Questo elimina il limite di ricorsione di Python e riduce l'overhead per frame, al costo di un codice più complesso. La DFS iterativa con uno stack esplicito che abbiamo visto in precedenza segue esattamente questo schema.
# Recursive inorder traversal -> iterative with explicit stack
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorder_iterative(root):
result = []
stack = []
curr = root
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
result.append(curr.val)
curr = curr.right
return result
root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6))
print(inorder_iterative(root)) # [1, 2, 3, 4, 6]Riepilogo: stack delle chiamate e spazio
Lo stack delle chiamate è la struttura dati nascosta alla base di ogni ricorsione. La sua profondità corrisponde alla complessità spaziale dell'algoritmo ricorsivo. Python la limita a circa 1000, quindi gli algoritmi con profondità di ricorsione O(n) richiedono un limite aumentato, rischioso, oppure una riscrittura iterativa. Quando scrive codice ricorsivo durante un colloquio, dichiari sempre la complessità spaziale dovuta allo stack delle chiamate: «Questo usa spazio O(n) per la profondità della ricorsione» oppure «O(log n) per una visita di un albero bilanciato».
Verifica rapida
Verifichi la sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha appreso che: ogni chiamata ricorsiva crea un frame dello stack contenente le variabili locali e l'indirizzo di ritorno; la profondità massima dello stack corrisponde alla complessità dello spazio ausiliario della ricorsione; e il limite di ricorsione di Python (circa 1000) rende rischiosi per valori elevati di n gli algoritmi con profondità O(n): li si deve convertire in iterativi usando uno stack esplicito. Ora confronteremo le soluzioni ricorsive e iterative e discuteremo quando usare ciascuna.
Domande Frequenti
La lezione «Visualizzare lo stack delle chiamate» è gratuita?
Sì — il testo completo di «Visualizzare lo stack delle chiamate» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Visualizzare lo stack delle chiamate»?
Usi il modulo sys di Python e il tracing con print per osservare la crescita e la riduzione degli stack frame e comprendere i rischi di stack overflow nella ricorsione profonda Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «Visualizzare lo stack delle chiamate»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Schema della ricorsione: caso base, fiducia, costruzione
- Visualizzare lo stack delle chiamate
- Compromessi tra ricorsivo e iterativo
- Memoisation: memorizzare nella cache i risultati ricorsivi