La ricorsione in C++

Ricorsione

  Il concetto di ricorsione può essere analizzato nelle diverse fasi dell'attività di programmazione; la si può utilizzare nella fase di analisi del problema, nella fase di progetto e nella fase di realizzazione.
ANALISI: L'idea di base della ricorsione è quella di definire un nuovo concetto mediante se stesso.
PROGETTO: La defionizione ricorsiva è tradotta con un algoritmo in cui una procedura (funzione) richiama se stessa

In una definizione ricorsiva, come nell'algoritmo, possiamo sempre riconoscere due parti:
1. La Regola di base, che stabilisce la condizione terminale del processio di calcolo
2. La Regola induttiva, che definisce l'oggetto in termini di se stesso

Il C++ permette di creare algoritmi ricorsivi, grazie al meccanismo di chiamata a funzione nello Stack in Memoria centrale.
Le funzioni ricorsive possono essere:
• Dirette • Indirette Si dicono dirette quando la funzione richiama se stessa nel corpo del sottoprogramma
si dicono indirette quando il richiamo alla funzione non vine direttamente, ma attraverso un'altra funzione che contiene a sua volta quella iniziale.


Il meccanismo di calcolo di una funzione ricorsiva è suddiviso in tre fasi:
1. Successivi richiami della stessa funzione, finchè non è verificata la condizione contenuta nella regola base;
2. Calcolo della condizione terminale, definita nella regola di base;
3. Valutazione della funzione nelle diverse chiamate.
Il modello del tracciato di un processo ricorsivo è un albero binario dove la radice rappresentala regola di base mentre le due foglie sono la prima chiamata dela funzione e il risultato restituito al programma chiamante.


Vantaggi e Svantaggi
• Vantaggio: Leggibilità del codicesorgente
In pratica gli algoritmi ricorsivi sono semplici da scrivere e quindi da tradurre in un codice sorgente.
• Svantaggio: Impossibilità di realizzazione
In pratica non tutti i linguaggi di programmazione permettono di ralizzarla.
• Svantaggio: L'errore di traboccamento dello Stack
In pratica nelle ricorsioni con un numero elevato di "richiamate", si potrebbe verificare un overflow cioè che la memoria RAM trabocchi. Questo porta a bloccare l'esecuzione del programma e a provocare un errore di run-time.
• Svantaggio: Bassa efficenza
In pratica un programma efficente è "veloce" (bassi tempi di CPU) e occupa poco "spazio" (celle RAM). Una funzione ricorsiva è l'esatto opposto, "Lenta" e occupa "Spazio" nella RAM.

link originale:
http://www.devlabs.it/cplusplus-esercizi-e-teoria/C++/ricorsione.php

Commenti