Prolog fattoriale ricorsione

Question

Sto avendo difficoltà a capire il seguente programma fattoriale

fact1(0,Result) :- 
    Result is 1. 
fact1(N,Result) :- 
    N > 0, 
    N1 is N-1, 
    fact1(N1,Result1), 
    Result is Result1*N. 

Quando fact1 è chiamato nidificato all'interno della seconda fact1, non vuol dire che l'l'ultima riga, Result is Result1*N., non viene mai chiamato? O in Prolog l'ultima riga viene eseguita prima della chiamata ricorsiva?

Answer 1

No, la chiamata ricorsiva viene eseguita prima! Deve farlo, altrimenti l'ultima clausola non ha senso. L'algoritmo si rompe a:

factorial(0) => 1 
factorial(n) => factorial(n-1) * n; 

Come si può vedere, è necessario calcolare il risultato della ricorsione prima di moltiplicare in modo da restituire un valore corretto!

L'implementazione del prologo probabilmente ha un modo per abilitare la traccia, che consente di vedere l'intero algoritmo in esecuzione. Questo potrebbe aiutarti.

Answer 2

BTW una volta ottenuto il ricorsione base capito, tenta di raggiungere la ricorsione in coda, quando possibile, qui sarebbe:

factorial(N, R) :- factorial(N, 1, R). 
factorial(0, R, R) :- !. 
factorial(N, Acc, R) :- 
    NewN is N - 1, 
    NewAcc is Acc * N, 
    factorial(NewN, NewAcc, R). 

ricorsione in coda, a differenza della ricorsione utilizzato in precedenza, permette interprete/compilatore per irrigare contesto quando si passa alla fase successiva della ricorsione. Quindi supponiamo di aver calcolato factorial(1000), la tua versione manterrà 1000 contesti mentre la mia manterrà solo 1. Ciò significa che la tua versione alla fine non calcolerà il risultato desiderato ma si bloccherà semplicemente su un errore Out of call stack memory.

È possibile read more su di esso su wikipedia.

Answer 3

Un modo piuttosto semplice di farlo è questo:

fac(0,1). 
fac(N,F):- 
    N>0,N1 is N-1,fac(N1,F1),F is N*F1. 

Answer 4

In generale, @m09's answer è fondamentalmente ragione circa l'importanza della coda ricorsione.

Per il grande N, il calcolo del prodotto ha vinto in modo diverso! Pensa "albero binario", non "elenco lineare" ...

Proviamo entrambi i modi e confrontiamo i tempi di esecuzione. In primo luogo, di @ M09 factorial/2:

 
?- time((factorial(100000,_),false)). 
% 200,004 inferences, 1.606 CPU in 1.606 seconds (100% CPU, 124513 Lips) 
false. 

Avanti, lo facciamo albero in stile — utilizzando meta-predicatereduce/3 insieme lambda expressions:

 
?- time((numlist(1,100000,Xs),reduce(\X^Y^XY^(XY is X*Y),Xs,_),false)). 
% 1,300,042 inferences, 0.264 CPU in 0.264 seconds (100% CPU, 4922402 Lips) 
false. 

scorso, definiamo e l'uso dedicato predicato ausiliario x_y_product/3:

x_y_product(X, Y, XY) :- XY is X*Y. 

Cosa si ottiene? Facciamo il al cronometro!

 
?- time((numlist(1,100000,Xs),reduce(x_y_product,Xs,_),false)). 
% 500,050 inferences, 0.094 CPU in 0.094 seconds (100% CPU, 5325635 Lips) 
false. 

Answer 5

vorrei fare qualcosa di simile:

fact(0, 1). 
fact(N, Result):- 
    Next is N - 1, 
    fact(Next, Recursion), 
    Result is N * Recursion. 

e una versione di coda sarebbe come:

tail_fact(0, 1, 0).   /* when trying to calc factorial of zero */ 
tail_fact(0, Acc, Res):- /* Base case of recursion, when reaches zero return Acc */ 
    Res is Acc. 
tail_fact(N, Acc, Res):- /* calculated value so far always goes to Acc */ 
    NewAcc is N * Acc, 
    NewN is N - 1, 
    tail_fact(NewN, NewAcc, Res). 

Quindi, è possibile chiamare il:

ricorsiva non-coda metodo: fatto (3, Risultato).

metodo ricorsivo di coda: tail_fact (3, 1, Risultato).

Questo potrebbe aiutare;)

Answer 6

non tailer ricorsione:

fact(0,1):-!. 
    fact(X,Y):- Z=X-1, 
     fact(Z,NZ),Y=NZ*X. 

tailer ricorsione:

fact(X,F):- X>=0,fact_aux(X,F,1). 
fact_aux(0,F,F):-!. 
    fact_aux(X,F,Acc):- 
     NAcc=Acc*X, NX=X-1, 
    fact_aux(NX,F,NAcc). 

Answer 7

factorial(1, 1). 
factorial(N, Result) :- M is N - 1, 
factorial(M, NextResult), Result is NextResult * N. 

Answer 8

Caso base viene dichiarato. Le condizioni che N deve essere positiva e moltiplicare con il termine precedente.

factorial(0, 1). 
factorial(N, F) :- 
     N > 0, 
     Prev is N -1, 
     factorial(Prev, R), 
     F is R * N. 

Per eseguire:

fattoriale (-1, X).