Seguici su Telegram, ne vale la pena ❤️ ➡ @trovalost
Vai al contenuto

Ricorsione: come funziona questa tecnica di programmazione

Tag:
5/5 (2)

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.

Esempio di ricorsione: Triangoli di Sierpinski

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: la somma dei primi N numeri (in Python)

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 (soluzione iterativa). potremmo, invece, proporre una funzione

recursiveSum

con un parametro N di input, definita a sua volta 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 a questa funzione per n=5:
print(recursiveSum(5) )

Calcolo di un’area in maniera ricorsiva in Java

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, per capirci, 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 concepire la funzione 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;
}

Requisiti delle funzioni ricorsive

Morale della favola: quando si applica la ricorsione, in sostanza, è 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). Se viene mal definita o realizzata male, o concepita in modo teoricamente errato, può portare ad errori di vario genere oppure a loop infiniti (le chiamate ricorsive continuano per sempre, e la funzione non si risolve, non restituisce un risultato).

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, come abbiamo detto, in un loop infinito.

(immagine di copertina: PiAndWhippedCream – Opera propria, Pubblico dominio, https://commons.wikimedia.org/w/index.php?curid=2155993)

👇 Da non perdere 👇

Questo portale esiste da 4455 giorni (12 anni), e contiene ad oggi 5762 articoli (circa 4.609.600 parole in tutto) e 13 servizi online gratuiti. – Leggi un altro articolo a caso

Ti sembra utile o interessante? Vota e fammelo sapere.

Leggi anche:
Questo sito contribuisce alla audience di sè stesso.
Il nostro network informativo: Lipercubo.it - Pagare.online - Trovalost.it.