Ricorsione: come funziona questa tecnica di programmazione

Aggiornato il: 27-06-2022 06:00

Definizione ricorsione

La ricorsione è una tecnica di programmazione in vari linguaggi per ridurre il numero di righe che devono essere scritte, effettuare compiti complessi con la tecnica della decomposizione e migliorare l’efficenza del codice. La ricorsione (in inglese recursion) consiste in una chiamata ad una singola funzione che risolve le singole istanze dei sottoproblemi, ricorrendo ad un approccio algoritmico top down (dal caso generale al / ai caso / i particolare/i).

In informatica teorica sono molto numerosi gli algoritmi che funzionano mediante ricorsione: le torri di Hanoi, ad esempio, la ricerca dei nodi in un grafo mediante Depth First Search, la determinazione di un cammino ottimale su un albero e cosଠvia. Grazie alla ricorsione si possono inoltre generare “facilmente” strutture dati definite in funzione di se stesse che si presentano, visivamente, come pattern ripetuti più volte o frattali.

Un esempio classico sono i triangoli di Sierpinski, che si possono adeguare a qualsiasi forma base si voglia, inclusa quella di un cagnolino (clicca per ingrandire). Ciò che cambia non è l’immagine in piccolo bensଠ“solo” la forma che assume l’immagine a livello di configurazione “vista dall’alto”, per dirla in modo intuitivo e poco tecnico quanto efficace.

Sierpinski dog
Di Stevo-88 – Opera propria, Pubblico dominio, https://commons.wikimedia.org/w/index.php?curid=2215405

La ricorsione viene usata in parte per scansionare strutture dati per le quali non sia nota a priori la dimensione o la forma, e si possono adeguare (salvo eccezioni OutOfMemory) per scansionare dati di pagine web mediante crawler, almeno in alcuni casi.

Esempio facile di ricorsione

Poniamo di fare uso del linguaggio di programmazione Python, che introduce le funzioni con la parola chiave def e che ci servirà  a fornire una somma dei primi N numeri naturali. Se ad esempio inseriamo N=5 in input, l’algoritmo effettuerà  la somma di 1+2+3+4+5 restituendo come risultato 15. Potremmo effettuare un ciclo FOR da 1 fino ad N, ovviamente, e questa sarebbe la risoluzione iterativa del problema basata sulla programmazione imperativa classica. potremmo, invece, proporre una funzione recursiveSum con un parametro N di input, definita come segue:

  • nel caso base, cioè se N<=1, restituisci il valore di N (condizione di uscita);
  • in tutti gli altri casi, restituisci la funzione recursiveSum con N-1 come parametro di ingresso, che genererà  una catena di chiamate alla funzione somma con una singola funzione, per cui ad esempio N=5 genererà  5 + recursiveSum(4) + … + 1 = 15, come ci aspettavamo.

In Python possiamo effettuare la cosa in questi termini:

def recursiveSum(n):     if n <= 1:         return n     return n + recurSum(n - 1)
Ecco quindi la chiamata al codice con n=5:
print(recursiveSum(5))

Calcolo di un’area in maniera ricorsiva

Supponiamo ora, giusto per vedere un altro esempio molto simile di algoritmo ricorsivo, di voler calcolare il numero di simboli [] presenti in un triangolo costruito in questo modo:

 []
 [][]
 [][][]
 [][][][]

in cui ammettiamo come ipotesi che ogni [] abbia dimensione dell’area pari a 2. Possiamo pertanto definire una prima condizione IF di questo tipo:

if (n==1) return 2;

ovvero se c’è solo un quadrato (if n==1) l’area sarà  2 (return 2); se invece ne abbiamo più di uno toccherà  richiamare ricorsivamente la funzione, applicandola alla somma di n + sommaCumulativa(n-1). Tanto per vedere la stessa cosa con un altro linguaggio, immaginiamo di scrivere sommaCumulativa (n) in linguaggio Java:

public static int sommaCumulativa( N ) {
        int somma;     
        if (N == 1)
            somma = 2;   //condizione cosiddetta di uscita
        else
            somma = N + sommaCumulativa(N - 1); // chiamata ricorsiva
                          
        return somma;
    }

Quando si applica la ricorsione, è necessario che l’operazione sia ben definita e calcolabile (nei casi visti, una somma: diversamente dobbiamo accertarci di poter effettuare l’operazione su una singola coppia e poi, una volta capito come fare, provare a generare la funzione ricorsiva). La ricorsione è potente ma va utilizzata con cura, sia perchè è facile sbagliarsi nell’implementarla sia perchè richiede un dispendio di memoria RAM considerevole, dato che deve riallocare tanti pezzi di memoria per quanti sono i sottoproblemi.

La chiamata ricorsiva deve intervenire su un dato successivo della lista (di “dimensione” inferiore, tecnicamente parlando), e deve garantire la terminazione dell’algoritmo stesso che altrimenti entrerebbe in un loop infinito. (immagine di copertina: PiAndWhippedCream – Opera propria, Pubblico dominio, https://commons.wikimedia.org/w/index.php?curid=2155993)



Questo blog pubblica contenuti ed offre servizi free da 11 anni. – Leggi un altro articolo a caso – Per informazioni contattaci
5/5 (2)

Ti sembra utile o interessante? Vota e fammelo sapere.

Ricorsione: come funziona questa tecnica di programmazione
800px SierpinskiTriangle.svg
Torna su