comprensione ricorsione di base

Question

public static void main (String[] args) 
{ 
    System.out.println(factorial(5)); 
} 

public int factorial(int n) 
{ 
    if(n <= 1){ 
     return 1; 
    } 
    else{ 
     return n * factorial(n - 1); 
    } 
} 

Ho scritto quanto sopra direttamente qui, quindi potrebbe non essere compilato ma pensarlo.

Qualcuno può tranquillamente spiegare come funziona in questo modo che come viene memorizzato? Si inizia calcolando 5 * (5-1), poi giù a 4 * (4-1) poi 3 * (3-1) ..... finché non arriva a 1 che restituirà solo 1 a destra? mi dispiace per essere così abbozzato vorrei solo essere interessati a scoprire come funziona esattamente

grazie

ma come funziona fuori - diventa i valori per le singole fasi

5 * (5 -1) 4 * (4-1) ... ... ...

come sono questi conservati e poi recuperate indietro o mi sto perdendo qualcosa?

Answer 1

immaginate di essere il computer, e qualcuno ti porge una carta con

factorial(3) 

scritto su di esso. Quindi esegui la procedura, osservando l'argomento. Dal momento che è> 1, si scrive

factorial(2) 

su un altro pezzo di carta e "mano a voi stessi", in attesa fino a quando si ottiene la risposta a quello prima di procedere.

Ancora una volta si esegue la procedura.Dal 2 è ancora> 1 si scrive

factorial(1) 

su un altro pezzo di carta e la mano a voi stessi, in attesa fino a quando si ottiene la risposta a questa domanda prima di procedere.

Ancora una volta, si esegue la procedura. Questa volta l'input è 1, quindi prendi il primo ramo e restituisci 1. L'invocazione che stava elaborando factorial (2) ora ha una risposta, quindi moltiplica 2 per quella risposta (1) e ritorna. Ora l'invocazione che stava gestendo factorial (3) ottiene la sua risposta (2) e la moltiplica per 3, dando 6. Quindi restituisce la risposta alla persona che ha iniziato l'intera operazione.

Se immaginate di aver tenuto i pezzi di carta in pila davanti a voi mentre lavoravate, si tratta di una visualizzazione dello "stack" nella memoria del computer. Ogni invocazione ricorsiva memorizza il parametro (e le eventuali variabili temporanee) sul proprio pezzo di carta (frame dello stack) disposto letteralmente come stack pushdown proprio come i documenti, uno sopra l'altro.

Answer 2

.... quindi 3 * (3-1) ..... fino a 1 che restituirà 1 giusto?

destra, ma restituisce che '1' per il prossimo per durare invocazione, che moltiplica per due, di ritorno '2' ... alla next-to-next-to-scorso, che moltiplicherà per tre .....

Answer 3

Sì hai ragione nel codice, esso controlla prima il valore di n se è inferiore o uguale a 1, questo è ciò che viene indicato come il vostro caso di base. Sono importanti, dicono alla tua funzione ricorsiva quando fermarsi.

Se il valore di n non è inferiore o uguale, restituisce il valore di n moltiplicato per la chiamata ricorsiva di factorial ma con il valore n-1 alto fino a raggiungere è caso base: if (n <= 1) dove torna 1

Il caso base è stato impostato dalla definizione fattoriale di 0! e 1!, che sono entrambi pari a 1.

Forse questo diagramma potrebbe aiutare a capire come funzionano le chiamate.

5 * fact(5-1) -> 
      4 * fact(4-1) -> 
        3 * fact(3-1) -> 
           2 * fact(1) 
             1 

Quale è lo stesso di 5! o 5 x 4 x 3 x 2 x 1

Spero che questo aiuti.

Answer 4

Stai chiedendo come funziona la ricorsione internamente? La risposta di una frase è che ogni thread ha uno "stack di chiamate" e ogni volta che viene chiamato un metodo, una nuova voce viene inserita in questo stack, che contiene informazioni su quale metodo viene chiamato e quali sono gli argomenti. Quando il metodo è finito, riporta il suo valore di ritorno sullo stesso stack e il metodo di chiamata lo rimuove. Così al suo apice il vostro stack sarà simile

fattoriale (1) chiamato da fattoriale (2) chiamato da fattoriale (3) chiamato da fattoriale (4) chiamato da fattoriale (5)

Il Wikipedia article sugli stack di chiamate sembra piuttosto accurato a prima vista.

Answer 5

1. Nella chiamata iniziale a fattoriale, n = 5, e viene inserito nello stack.
2. Quindi il resto viene attivato così 4 è passato a fattoriale, ed è anche inserito nello stack.
3. Quindi il else viene attivato in modo che 3 sia passato a fattoriale, ed è anche inserito nello stack.
4. Quindi il resto viene attivato in modo che 2 sia passato a fattoriale, ed è anche inserito nello stack.
5. Quindi il resto viene attivato in modo che 1 sia passato a fattoriale ed è anche inserito nello stack.
6. Quindi il else viene attivato in modo che 0 sia passato a fattoriale, ed è anche inserito nello stack.
7. Il se viene attivato e 1 è restituito al fattoriale chiamante.
8. Il se viene attivato e 2 * 1 è restituito al fattoriale chiamante.
9. Il se viene attivato e 3 * 2 è restituito al fattoriale chiamante.
10. Il se viene attivato e 4 * 3 è restituito al fattoriale chiamante.
11. Il se viene attivato e 5 * 4 è restituito al fattoriale chiamante.

Lo stack viene pulito anche se diventa troppo noioso per digitare. Essenzialmente tutti i valori di una chiamata al metodo vengono inseriti nello stack e prelevati dallo stack sul metodo restituito. Questo li tiene separati tra le chiamate ricorsive.

Answer 6

È importante notare che la "ricorsione" funziona in modo diverso in java (un linguaggio procedurale) rispetto a Haskell o F # (lingue funzionali).

In Java quando invochiamo la ricorsione lo facciamo valutando l'albero delle espressioni e risolvendo ogni parte di esso fino a quando non determiniamo il valore di ciascuna parte dell'espressione. Se abbiamo bisogno di invocare un'altra funzione, inseriamo un segnaposto per tutti i valori intermedi in quel punto e quindi iniziamo a costruire un nuovo albero di espressioni per la nuova funzione.

Nel caso della ricorsione, ciò che stiamo facendo è effettuare una chiamata alla stessa funzione, si spera con diversi valori di terminazione, che devono essere risolti prima di poter completare la valutazione dell'espressione corrente. Queste espansioni vengono concatenate ripetutamente fino a quando accade una delle due cose 1) Raggiungiamo un'espressione terminante che restituisce il controllo al chiamante (la prima parte del tuo se in questo caso), o esauriamo la nostra capacità di mettere valori intermedi nello storage e noi restituisce un'eccezione (overflow dello stack).

Nel primo caso iniziamo a risolvere ciascuno degli alberi di espressione dalla cima dello stack, procedendo all'indietro fino a quando non ci sono più voci dello stack, a quel punto l'albero delle espressioni si risolve sul valore finale restituito.

La risposta di Jim è un'eccellente metafora fisica per questo.

Answer 7

E 'difficile indovinare esattamente quale parte della ricorsione hai difficoltà con, ma ho intenzione di andare fuori questa parte della tua domanda:

fino a quando non arriva a 1 che sarà solo tornare 1 destra?

Sto indovinando vuoi dire, "se sarà solo tornare 1, perché è il risultato della funzione non 1?"

Considerare che quando si ritorna da una funzione (in questo caso fattoriale) si restituisce un valore a chiunque abbia richiesto originariamente.

Se dico "darmi fattoriale (5)", quindi fattoriale (5) verrà me restituire un valore, ma prima che mi può restituire il valore ha chiedere fattoriale (4) per il suo valore, fattoriale (5) dice in sostanza "dammi fattoriale (4) così posso moltiplicarlo per 5 e restituirlo al tizio che ha chiesto fattoriale (5)". Ora fattoriale (4) restituirà il suo valore a fattoriale (5) che può moltiplicarlo per n e restituire il suo valore a me. Ricordiamo, I non ho chiesto il valore di factorial (4), non mi interessa nemmeno, e non è tornato da me, è tornato a fattoriale (5).

Nel momento in cui si preme fattoriale (1) si avranno fattoriali (2), fattoriali (3), fattoriali (4) e fattoriali (5) tutti in attesa di ottenere una risposta. Fattoriale (1) restituirà il suo valore (che è 1, a causa del tuo caso base) a fattoriale (2), che può finalmente tornare fattoriale (3) e così via, a quel punto la ricorsione si completerà e tu riporta indietro il valore di factorial (5).

Answer 8

Un approccio pratico che richiede un buon IDE (Eclipse, NetBeans, IntelliJ):

Aggiungere un punto di interruzione alla linea che legge return 1 e eseguire il debug dell'applicazione. Quando si ferma, guarda la traccia dello stack. Vedrai che il metodo fattoriale è stato chiamato più volte.

La vista Debug di eclissi mostra il thread sospeso e uno stack con sei voci, ogni riga rappresenta una riga di codice in cui viene chiamato un altro metodo (eccetto per la voce in alto, ovvero il punto di interruzione). fattoriale appare cinque volte, è possibile selezionare ogni riga e vedere il valore di n nella vista Variabile (questo è di base e dovrebbe funzionare sull'altro IDE in un modo simile).

Questo dovrebbe dare un'altra idea di come metodo ricorsivo chiama lavoro (e il motivo per cui si riceve un errore di memoria quando non si definiscono i criteri di uscita correttamente;))