Ricorsione:
In termini di programmazione una funzione ricorsiva può essere definita come una routine che si chiama direttamente o indirettamente.
Usando l’algoritmo ricorsivo, alcuni problemi possono essere risolti abbastanza facilmente. Torri di Hanoi (TOH) è uno di questi esercizi di programmazione. Prova a scrivere un algoritmo iterativo per TOH. Inoltre, ogni programma ricorsivo può essere scritto utilizzando metodi iterativi (Fare riferimento alle strutture dati di Lipschutz).
Matematicamente ricorsione aiuta a risolvere alcuni enigmi facilmente.,
Ad esempio, una domanda di intervista di routine,
In un gruppo di N persone, ogni persona stringerà la mano con l’altra persona solo una volta. In totale quante scosse di mano accadrebbe?
Soluzione:
Può essere risolto in diversi modi, grafici,ricorsioni, ecc. Vediamo, come ricorsivamente può essere risolto.
Ci sono N persone. Ogni persona si stringe la mano l’una con l’altra solo una volta. Considerando N-esima persona, (s)deve stringere la mano con (N-1) persone. Ora il problema si è ridotto a una piccola istanza di (N-1) persone. Assumendo TN come totale shake-hands, può essere formulato in modo ricorsivo.,
TN = (N-1) + TN-1
Risolvendolo ricorsivamente si ottiene una serie aritmetica, che può essere valutata in N(N-1)/2.
Esercizio: In un gruppo di N coppie, solo un genere (maschio o femmina) può stringere la mano a tutti. Quante strette di mano accadrebbe?
Di solito i programmi ricorsivi si traducono in scarse complessità temporali. Un esempio è la serie di Fibonacci. La complessità temporale del calcolo dell’n-esimo numero di Fibonacci utilizzando la ricorsione è di circa 1,6 n. Significa che lo stesso computer impiega quasi il 60% in più di tempo per il prossimo numero di Fibonacci. L’algoritmo ricorsivo di Fibonacci ha sovrapposto i sottoproblemi., Esistono altre tecniche come la programmazione dinamica per migliorare tali algoritmi sovrapposti.
Tuttavia, pochi algoritmi, (ad esempio merge sort, quick sort, ecc.), producono una complessità temporale ottimale usando la ricorsione.
Caso base:
Un requisito critico delle funzioni ricorsive è il punto di terminazione o il caso base. Ogni programma ricorsivo deve avere il caso base per assicurarsi che la funzione terminerà. Il caso base mancante determina un comportamento imprevisto.,
Diversi modi di scrivere funzioni ricorsive
Funzione che si chiama: (modo diretto)
La maggior parte di noi conosce almeno due diversi modi di scrivere programmi ricorsivi. Dato di seguito è torri di Hanoi codice. È un esempio di chiamata diretta.

Output:

Move the disk 1 from S to DMove the disk 2 from S to AMove the disk 1 from D to AMove the disk 3 from S to DMove the disk 1 from A to SMove the disk 2 from A to DMove the disk 1 from S to D

La complessità temporale di TOH può essere calcolata formulando il numero di mosse.
Dobbiamo spostare i primi dischi N-1 dall’origine all’ausiliario e dall’Ausiliario alla destinazione, cioè i primi dischi N-1 richiedono due mosse. Un’altra mossa dell’ultimo disco dall’origine alla destinazione., Matematicamente può essere definito ricorsivamente.
MN = 2MN-1 + 1.
Possiamo facilmente risolvere la relazione ricorsiva sopra (2N-1), che è esponenziale.
Ricorsione usando la chiamata di funzione reciproca: (modo indiretto)
Chiamata indiretta. Anche se meno pratico, una funzione può chiamare un’altra funzione che inturn chiama la funzione precedente. In questo caso entrambe le funzioni dovrebbero avere il caso base.
Programmazione difensiva:
Possiamo combinare tecniche di codifica difensiva con la ricorsione per funzionalità graziose di applicazione., Di solito la programmazione ricorsiva non è consentita in applicazioni critiche per la sicurezza, come controlli di volo, monitoraggio sanitario, ecc. Tuttavia, è possibile utilizzare una tecnica di conteggio statico per evitare chiamate incontrollate (NON nei sistemi critici per la sicurezza, può essere utilizzato in sistemi soft real time).

La profondità di callDepth dipende dalla dimensione del frame dello stack di funzioni e dalla dimensione massima dello stack.
Ricorsione usando i puntatori di funzione: (modo indiretto)
La ricorsione può anche essere implementata con i puntatori di funzione. Un esempio è il gestore del segnale nei sistemi di reclamo POSIX., Se il gestore causa l’attivazione dello stesso evento a causa del quale il gestore viene chiamato, la funzione rientrerà.