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.
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:
Usa il codice
189ed7ca010140fc2065b06e3802bcd5
per ricevere 5 € dopo l'iscrizione
- 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)
(
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)
👇 Contenuti da non perdere 👇
- Cellulari 📱
- Internet 💻
- Marketing & SEO 🌪
- monitoraggio servizi online 📈
- Programmare 🖥
- Svago 🎈
- WordPress 🤵
- 💬 Il nostro canale Telegram: iscriviti
- 🟡 Algoritmo di Euclide: cos’è e come funziona
- 🟡 Cos’è un dominio di quarto livello?
- 🔴 Sito CloudFlare down – Funziona CloudFlare? Verifica qui