Ricorsione — Informatica, 14–17 anni

Come risolvere un problema creando una versione più piccola dello stesso problema, con un punto chiaro in cui il processo termina.

Idea

La ricorsione si verifica quando una funzione risolve un compito chiamando sé stessa con un dato più piccolo o semplice. Serve anche un caso base: una situazione abbastanza semplice da risolvere direttamente. Ogni chiamata si avvicina a quel caso, come aprire una scatola più piccola dentro un’altra fino all’ultima.

Perché conta

Alcuni problemi contengono copie più piccole di sé stessi. Le cartelle contengono cartelle, gli alberi genealogici hanno rami e un labirinto può contenere sezioni da esplorare. La ricorsione descrive bene queste forme, perché riusa le stesse istruzioni invece di scrivere codice per ogni profondità possibile.

Esempio svolto

Per calcolare 4 fattoriale, definiamo fact(1)=1 come caso base. Poi fact(4)=4×fact(3), fact(3)=3×fact(2) e fact(2)=2×fact(1). Sostituendo dal basso verso l’alto otteniamo 2×1=2, 3×2=6 e 4×6=24: quindi 4!=24.

Errore comune

Un errore comprensibile è scrivere la chiamata alla funzione stessa e dimenticare il caso base o il passo che porta a esso. Il codice continua così a chiamarsi senza fine, perché il computer non può indovinare quando il compito è finito. Anche con un caso base, un passo sbagliato può far crescere il dato invece di ridurlo.

Dove si usa

I browser, gli strumenti per i file e i sistemi di ricerca esplorano spesso cartelle annidate o pagine collegate usando idee ricorsive. Anche un programma per immagini può elaborare una foto dividendola in regioni più piccole e dividendole ancora. La ricorsione è utile perché la stessa azione vale a ogni livello finché una regione è abbastanza piccola.

Continua a esplorare

Altre lingue

Caricamento di MyLeoNes™…