Pensare ricorsivamente: caso base e ricorsione
Scomporre un problema in copie più piccole
Pensare ricorsivamente: caso base e ricorsione è 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.
Che cosa significa ricorsione
La ricorsione è una funzione che risolve un problema chiamando sé stessa su una parte più piccola, finché tale parte non è abbastanza piccola da poter essere risolta direttamente. 🌀
Si fidi della copia più piccola
Il concetto fondamentale è il salto di fiducia: supponga che la chiamata ricorsiva funzioni già sull'input più piccolo, poi costruisca la risposta a partire da quel risultato.
Ogni ricorsione richiede un caso base
Il caso base è l'input più piccolo a cui si risponde senza ricorrere. Senza di esso, la funzione chiamerà sé stessa all'infinito e andrà in crash.
Il caso ricorsivo
Il caso ricorsivo riduce il problema e richiama sé stesso sulla versione più piccola. Ogni chiamata deve avvicinarsi al caso base.
Il fattoriale come primo esempio
Qui il fattoriale mostra entrambe le parti: un caso base quando n è zero e una chiamata ricorsiva su n meno uno.
def fact(n):
if n == 0:
return 1
return n * fact(n - 1)Come funziona lo stack delle chiamate
Ogni chiamata resta in attesa nello stack delle chiamate finché la chiamata interna non restituisce il risultato. La chiamata più profonda termina per prima, poi le risposte risalgono lo stack.
Monitori la profondità della ricorsione
Python limita per impostazione predefinita la profondità della ricorsione a circa 1000. Nella ricorsione profonda delle gare, usi sys.setrecursionlimit per evitare un errore a runtime.
import sys
sys.setrecursionlimit(300000)Faccia progressi a ogni chiamata
Una ricorsione corretta riduce sempre l'input, avvicinandolo al caso base. Se ripassa anche una sola volta dalla stessa dimensione, entra in un ciclo infinito. ⚠️
Sommi ricorsivamente una lista
Questa somma ricorsiva rimuove il primo elemento, poi si affida alla chiamata per aggiungere il resto della lista.
def total(a):
if not a:
return 0
return a[0] + total(a[1:])Gli alberi di ricorsione mostrano i rami
Quando una funzione effettua più di una chiamata, il lavoro forma un albero di ricorsione. Le sue dimensioni indicano il costo totale.
Il lavoro ripetuto può essere lento
La versione ingenua di Fibonacci ricalcola gli stessi valori più e più volte, ottenendo un tempo esponenziale. Memorizzare queste risposte in cache risolve subito il problema.
Verifica rapida
Cosa succede se una funzione ricorsiva non ha un caso base?
Riepilogo: due parti, un'idea
Ha imparato che la ricorsione ha bisogno di un caso base per fermarsi e di un caso ricorsivo che riduca l'input. Si affidi alla chiamata sul problema più piccolo e il resto verrà di conseguenza. 🎯
Domande Frequenti
La lezione «Pensare ricorsivamente: caso base e ricorsione» è gratuita?
Sì — il testo completo di «Pensare ricorsivamente: caso base e ricorsione» è 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 «Pensare ricorsivamente: caso base e ricorsione»?
Scomporre un problema in copie più piccole 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 «Pensare ricorsivamente: caso base e ricorsione»?
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
- Pensare ricorsivamente: caso base e ricorsione
- Generare tutti i sottoinsiemi
- Permutazioni e idea delle N regine
- Potare per superare il limite di tempo