Ricorsione e metodo dell'albero ricorsivo
Tracci le chiamate ricorsive negli alberi, applichi il teorema fondamentale delle ricorrenze e ricavi le complessità temporali di merge sort, fattoriale e varianti di Fibonacci
Ricorsione e metodo dell'albero ricorsivo è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 3 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 DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.
La ricorsione e lo stack delle chiamate
Quando una funzione chiama se stessa, ogni chiamata aggiunge un frame dello stack, che si accumulano fino al raggiungimento del caso base, dopodiché vengono rimossi. Visualizzare questo processo è il primo passo per analizzare la ricorsione.
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'albero della ricorsione per Fibonacci
Un albero della ricorsione espande ogni chiamata nelle chiamate che essa genera. Il Fibonacci ingenuo si divide in due chiamate a ogni passaggio, creando un albero di circa 2^n nodi: è O(2^n). Veda il codice.
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 1Individuare i sottoproblemi ripetuti
In quell'albero, le stesse chiamate, come fib(3), si ripetono lungo rami diversi. Questi sottoproblemi sovrapposti indicano che è opportuno usare la memoization, che riduce O(2^n) a 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 21L'albero della ricorsione del merge sort
L'albero del merge sort ha log n livelli e a ogni livello esegue complessivamente O(n) operazioni: ogni elemento viene visitato una volta. Moltiplicando i due valori si ottiene O(n log n). Veda il codice.
# 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)=384Il teorema del master
Il teorema del master risolve T(n) = a*T(n/b) + O(n^d) attraverso tre casi. Per il merge sort (a=2, b=2, d=1) restituisce O(n log n). Memorizzi i tre casi per l'esame.
# 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...Disegnare alberi di ricorsione passo dopo passo
Per disegnare un albero della ricorsione: metta T(n) in cima, espanda ogni chiamata, sommi il lavoro a ogni livello e poi moltiplichi per il numero di livelli. Si eserciti finché il procedimento non diventa automatico.
# 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)}')Ricorsione esponenziale: i sottoinsiemi
Generare tutti i sottoinsiemi richiede O(2^n): ce ne sono esattamente 2^n, quindi non è possibile fare meglio. Ogni elemento può essere incluso o escluso, creando un albero binario di scelte. Veda il codice.
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)Ricorsione in coda e ottimizzazione
La ricorsione in coda si verifica quando la chiamata ricorsiva è l'ultimo passaggio. Alcuni linguaggi riutilizzano il frame in questo caso, ma Python non lo fa: le ricorsioni profonde causano comunque un overflow. Usi invece un ciclo.
# 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)) # 3628800Complessità spaziale della ricorsione
Ogni chiamata ricorsiva mantiene un frame, quindi la ricorsione richiede spazio O(profondità). La ricorsione lineare è O(n); la DFS su un albero bilanciato è O(log n). Se la ricorsione diventa troppo profonda, si verifica un 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 framesL'albero della ricorsione del quick sort
Il quick sort è O(n log n) con un buon pivot, ma con un pivot sfavorevole su un input ordinato degrada a O(n^2). Per questo è importante rendere casuale la scelta del pivot. Veda il codice.
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])) # sortedFunzione potenza: ricorsione log n
Il calcolo ingenuo di x^n richiede O(n) moltiplicazioni, ma il quadrato dimezza il lavoro a ogni passaggio: x^n = (x^(n/2))^2. Si ottiene così un netto O(log n): il dimezzamento in azione. Veda il codice.
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=10Verifica rapida
Verifica rapida: dimostri ciò che il metodo dell'albero della ricorsione le ha insegnato. Una domanda, si prenda il tempo necessario. 🌳
Riepilogo della lezione
Riepilogo: un albero della ricorsione rivela il lavoro complessivo, il teorema del master risolve le ricorrenze divide et impera e la ricorsione richiede spazio nello stack pari a O(profondità).
Domande Frequenti
La lezione «Ricorsione e metodo dell'albero ricorsivo» è gratuita?
Sì — il testo completo di «Ricorsione e metodo dell'albero ricorsivo» è 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 DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Ricorsione e metodo dell'albero ricorsivo»?
Tracci le chiamate ricorsive negli alberi, applichi il teorema fondamentale delle ricorrenze e ricavi le complessità temporali di merge sort, fattoriale e varianti di Fibonacci Eserciti DSA 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 DSA Interview Prep?
Non è richiesta alcuna esperienza precedente. DSA 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 3 di 4.
Quanto tempo richiede la lezione «Ricorsione e metodo dell'albero ricorsivo»?
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 DSA Interview Prep?
Sì. Ogni lezione DSA 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
- La notazione Big-O dalle basi
- Analizzare cicli e cicli annidati
- Ricorsione e metodo dell'albero ricorsivo
- Complessità spaziale e compromessi