Schema della ricorsione: caso base, fiducia, costruzione
Applichi il metodo in tre passaggi per scrivere soluzioni ricorsive corrette per fattoriale, potenza e somma delle cifre senza tracciare ogni chiamata
Schema della ricorsione: caso base, fiducia, costruzione è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 1 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.
Perché la ricorsione sembra difficile
La maggior parte dei principianti cerca di seguire mentalmente ogni chiamata ricorsiva, cosa che diventa presto opprimente anche con una ricorsione profonda appena cinque livelli. L'approccio professionale consiste nell'usare un framework in tre passaggi — caso base, fiducia e costruzione — che consente di scrivere funzioni ricorsive corrette senza simulare mentalmente l'intero albero delle chiamate.
Questo framework viene talvolta chiamato salto di fiducia: si presume che la funzione funzioni su input più piccoli e si usa questa assunzione per costruire la soluzione per input più grandi.
Passaggio 1: Definire il caso base
Il caso base è l'input più semplice per il quale la risposta è nota senza ricorrere a ulteriore ricorsione. Ogni funzione ricorsiva deve avere almeno un caso base; senza di esso, la funzione ricorre all'infinito (overflow dello stack). I buoni casi base sono: lista vuota, singolo elemento, n == 0, n == 1 oppure un problema che si riduce a un'identità banale.
Scriva prima il caso base, prima di qualsiasi logica ricorsiva. Lo individui chiedendosi: «Qual è la versione più semplice di questo problema a cui posso rispondere immediatamente?»
# 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')Passaggio 2: Fidarsi della chiamata ricorsiva
Il passo della fiducia è un atto di fede: supponga che la funzione funzioni già correttamente per qualsiasi input strettamente più piccolo di quello corrente. Non è necessario dimostrarlo ora per ogni input più piccolo: la dimostrazione per induzione lo garantisce. Chiami semplicemente la funzione sul sottoproblema più piccolo e si fidi del fatto che restituisca il risultato corretto.
È questo il passaggio che i principianti saltano, cercando invece di simulare mentalmente l'esecuzione. Resista a questa tentazione: una volta interiorizzato il metodo, esso si applica anche a ricorsioni di profondità arbitraria.
# 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])) # 14Passaggio 3: Costruire la soluzione
Il passo della costruzione combina il risultato affidabile del sottoproblema con il contributo dell'elemento corrente per produrre la risposta relativa all'input completo. Di solito consiste in una sola riga: applicare un'operazione all'elemento corrente e al risultato della chiamata ricorsiva. Costruzioni comuni: aggiungere alla somma, anteporre a una lista, incrementare il conteggio, combinare due risultati parziali.
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)) # 1024Applicare il metodo alla somma delle cifre
Problema: calcolare la somma delle cifre di un intero non negativo. Caso base: n == 0 → la somma è 0 (oppure n < 10 → n stesso). Fiducia: sumDigits(n // 10) restituisce la somma di tutte le cifre tranne l'ultima. Costruzione: aggiungere l'ultima cifra n % 10 al risultato ottenuto per affidamento. Il metodo produce la soluzione in tre passaggi dichiarativi.
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)) # 36Fibonacci: due sottoproblemi
Fibonacci richiede due chiamate ricorsive: fib(n-1) e fib(n-2). Applichi il metodo: i casi base sono fib(0) = 0 e fib(1) = 1. Fiducia: entrambe le chiamate a input più piccoli restituiscono i valori corretti di Fibonacci. Costruzione: restituire la loro somma. Questa implementazione ingenua ha complessità O(2^n): la correggeremo nella lezione sulla memoizzazione.
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,13Invertire ricorsivamente una stringa
Problema: invertire ricorsivamente una stringa. Caso base: stringa vuota o composta da un solo carattere: è già invertita. Fiducia: reverse(s[1:]) restituisce l'inversione di tutto ciò che segue il primo carattere. Costruzione: aggiungere il primo carattere alla fine del suffisso invertito. Il metodo fornisce una soluzione in tre righe.
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'Contare ricorsivamente le occorrenze
Problema: contare ricorsivamente le occorrenze di un valore cercato in una lista. Caso base: lista vuota: il conteggio è 0. Fiducia: count(lst[1:], target) restituisce il conteggio nella coda. Costruzione: aggiungere 1 se il primo elemento corrisponde al valore cercato, altrimenti aggiungere 0. A ogni passo ricorsivo ci si avvicina al caso base riducendo la dimensione della lista di 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)) # 3Verificare se una lista è ordinata
Problema: verificare ricorsivamente se una lista è ordinata in senso crescente. Caso base: una lista con 0 o 1 elemento è sempre ordinata. Fiducia: is_sorted(lst[1:]) indica se la coda è ordinata. Costruzione: la lista è ordinata se il primo elemento è <= il secondo E la coda è ordinata. Questo è un esempio chiaro in cui il passo di costruzione usa un AND logico tra due condizioni.
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])) # FalseRicerca binaria ricorsiva (ripresa)
La ricerca binaria espressa ricorsivamente tramite il metodo: caso base: lo > hi → elemento non trovato (restituire -1). Fiducia: la chiamata ricorsiva sulla metà corretta trova l'elemento cercato oppure restituisce -1. Costruzione: calcolare mid, confrontare e chiamare la metà appropriata. La forma ricorsiva mostra chiaramente la struttura divide et impera, anche se in produzione si preferisce la forma iterativa per usare spazio 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)) # -1Quando usare la ricorsione anziché l'iterazione
La ricorsione è ideale quando il problema si suddivide naturalmente in sottoproblemi dello stesso tipo (alberi, divide et impera, backtracking). L'iterazione è preferibile quando: la profondità della ricorsione è elevata (con rischio di overflow dello stack in Python, che per impostazione predefinita consente circa 1000 livelli), le versioni ricorsiva e iterativa sono altrettanto chiare oppure il problema consiste in un semplice ciclo (fattoriale, Fibonacci senza memoizzazione).
Una buona regola pratica: se disegnare un albero di ricorsione vi viene naturale, usate la ricorsione. Se l'albero è una linea retta (ricorsione terminale), convertitelo in iterazione.
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 overflowVerifica 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: il metodo in tre passaggi consiste in Caso base (risposta più semplice nota), Fiducia (supporre che il sottoproblema sia risolto) e Costruzione (combinare l'elemento corrente con il risultato ottenuto per affidamento); è necessario scrivere prima i casi base ed evitare di tracciare mentalmente interi alberi di chiamate; e si deve usare l'iterazione quando la profondità della ricorsione rischia di causare un overflow dello stack o quando le forme ricorsiva e iterativa sono altrettanto chiare. Ora visualizzeremo in dettaglio lo stack delle chiamate.
Domande Frequenti
La lezione «Schema della ricorsione: caso base, fiducia, costruzione» è gratuita?
Sì — il testo completo di «Schema della ricorsione: caso base, fiducia, costruzione» è 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 «Schema della ricorsione: caso base, fiducia, costruzione»?
Applichi il metodo in tre passaggi per scrivere soluzioni ricorsive corrette per fattoriale, potenza e somma delle cifre senza tracciare ogni chiamata 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 1 di 4.
Quanto tempo richiede la lezione «Schema della ricorsione: caso base, fiducia, costruzione»?
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