La ricorsione è un concetto potente nel campo della scienza informatica, ma può essere difficile per i neofiti da afferrare. Ricorsione comporta una funzione o un metodo più volte si invoca in un contesto diverso fino a quando un contesto di "base" viene raggiunto e restituito. In altre parole, per risolvere un problema, il programma recontexualizes come un problema leggermente diverso. Quando si implementa un algoritmo ricorsivo, sempre in considerazione la forma più semplice del problema e stabilire questo esempio semplificato come un "caso base", che tutte le altre versioni del problema saranno riferimento.

istruzione

1 Definire come intestazione di una funzione - il nome della funzione e dei suoi ingressi. Per esempio, una funzione che trova un numero particolare Fibonacci potrebbe apparire come segue:

fib (int n) {}

Qui, la funzione calcola il numero "ennesima" Fibonacci nella sequenza.

2 Annotare come la funzione sarà chiamato genericamente. Per esempio, quando si chiama fib (), si utilizzerà un intero come argomento e registrare il numero intero che calcola:

int result = fib (x);

3 Definire il "caso base" del problema ricorsione. Ci possono essere più casi di base. Come la sequenza di Fibonacci richiede due numeri, avrete bisogno di due casi di base per attuare la sua soluzione.

if (n == 0) return 0;
if (n == 1) return 1;

4 Definire il passo ricorsiva del problema ricorsione come una versione più piccola, più semplice dello stesso problema, facendo riferimento all'esempio invocazione dal passo 2. Nel nostro esempio, la sequenza di Fibonacci è una sequenza matematica dove ogni numero della linea è la somma dei precedenti due numeri in sequenza. L'algoritmo per individuare un determinato numero di Fibonacci deve quindi invocare la stessa due volte, una per il numero precedente e una volta per il numero prima del numero precedente:

int risultato1 = fib (n-1);
int result2 = fib (n-2);

tornare risultato1 + risultato2;

5 Mettere insieme la funzione, ad esempio:

fib (int n) {
if (n == 0) return 0; // Caso base 1
else if (n == 1) return 1; // Caso base 2

else {// passo ricorsivo
int risultato1 = fib (n-1);
int result2 = fib (n-2);

tornare risultato1 + risultato2;
}

}

La struttura del "caso base" e "step ricorsivo" sarà lo stesso per tutte le funzioni ricorsive, se ci possono essere casi multipli di base e lunghi passaggi ricorsive.

Consigli e avvertenze

• Per aiutarvi a visualizzare una soluzione ricorsiva, a piedi attraverso input e ritorna con un problema di esempio del programma.
• Non importa come si sceglie di implementare la funzione, si deve sempre ritornare sua custodia base durante un certo punto durante l'esecuzione del programma. In caso contrario, la funzione non potrà mai smettere di chiamare se stesso!