Video: OCAML Tutorial 13/33: A Word on Recursion and Recursive Functions 2024
La ricorsione è una parola grande e spaventosa che si sente spesso sulla programmazione, specialmente il tipo frustrante di programmazione che insegnano all'università. Anche se è un concetto facile da descrivere, è davvero una vera mente quando si tratta di capire come funziona la ricorsione. La maggior parte delle persone lo accetta e va avanti. Non qui!
La ricorsione è fondamentalmente il processo di una funzione che si chiama. Ad esempio:
void funct (int x) {funct (x);}
In questa porzione di codice, si vede un terribile esempio di una funzione ricorsiva, ma serve a scopi illustrativi qui: Il funct () chiama se stessa. Questa è ricorsione. Ora, ciò che accade in questo esempio è fondamentalmente un ciclo infinito e, grazie a un qualcosa di tecnico, chiamato lo stack pointe r , il computer si arresta. Ma è solo un'illustrazione.
Affinché la ricorsione funzioni, la funzione deve avere una condizione di salvataggio, proprio come un loop. Pertanto, è necessario testare il valore passato alla funzione ricorsiva o il suo valore di ritorno. Ecco un esempio migliore di una funzione ricorsiva:
void ricorsione (int x) {if (x == 0) return; else {puts ("Boop!"); ricorsione (- x);}}
La funzione ricorsione () accetta il valore x . Se x è uguale a zero, la funzione si attiva. In caso contrario, la funzione viene richiamata di nuovo, ma il valore di x viene ridotto. L'operatore del prefisso di decremento viene utilizzato in modo che il valore di x venga ridotto prima di venga effettuata la chiamata.
La funzione ricorsione di esempio () sputa fondamentalmente il testo Boop! un determinato numero di volte. Quindi se ricorsione () viene chiamato con il valore 10, si vede quel testo visualizzato dieci volte.
La parte assurda della ricorsione è che la funzione continua a chiamarsi, avvolgendosi sempre più strettamente, come se fosse in una spirale. Nell'esempio precedente, la condizione x == 1 alla fine risolve quel pasticcio complicato, ritirandosi sempre più fino a quando la funzione non viene completata.
Il seguente codice mostra un programma completo che utilizza la funzione di ricorsione () di esempio.
#include void ricorsione (int x); int main () {ricorsione (10); return (0);} void ricorsione (int x) {if (x == 0) return; else {puts ("Boop!"); ricorsione (- x);}}
Una dimostrazione comune di ricorsione è una funzione fattoriale. Il fattoriale è il risultato della moltiplicazione di un valore per ciascuno dei suoi numeri interi positivi. Ad esempio:
4! = 4 × 3 × 2 × 1
Il risultato di questo fattoriale è 24. Il computer può anche fare questo calcolo, implementando un ciclo o creando una funzione ricorsiva.Ecco una funzione del genere:
int factorial (int x) {if (x == 1) return (x); else return (x * factorial (x-1));}
Come per le altre funzioni ricorsive, la funzione factorial () contiene una condizione di uscita: x == 1. In caso contrario, la funzione viene richiamata con un valore inferiore al valore corrente di x . Ma tutte le azioni si svolgono con i valori di ritorno.
