Prolog Fakultät Rekursion

Ich habe Probleme beim Verständnis der folgenden Faktoren-Programm

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

Wenn fact1 heißt geschachtelt innerhalb des zweiten fact1, heißt das nicht, dass das die Letzte Zeile, die Result is Result1*N., wird nie aufgerufen? Oder in Prolog bedeutet die Letzte Zeile, die ausgeführt werden, bevor der rekursive Aufruf?

InformationsquelleAutor CyberShot | 2012-03-06

6

Nein, der rekursive Aufruf passiert zuerst! Es muss, oder anderes, das Letzte Klausel ist sinnlos. Der Algorithmus bricht ab zu:
```
factorial(0) => 1
factorial(n) => factorial(n-1) * n;
```
Wie Sie sehen können, müssen Sie berechnen Sie das Ergebnis der Rekursion, bevor der Multiplikation, um wieder einen korrekten Wert!

Ihre prolog-Implementierung hat wahrscheinlich einen Weg, um die Ablaufverfolgung aktivieren, die ermöglichen würden Sie das ganze sehen-Algorithmus ausgeführt. Das könnte Ihnen helfen.

Tracing hilft immer!
Ich hoffe, du meinst factorial(0) => 1 🙂
Was factorial(-1)? Mit der obigen definition der Abfrage ?- fact1(-1,_). zu Recht versagt; factorial, wie es ist, nicht.

InformationsquelleAutor Carl Norum
12

BTW wenn Sie erst einmal die grundlegende Rekursion verstanden haben, versuchen zu erreichen, tail recursion, Wann immer möglich, hier wäre es:
```
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).
```
Tail recursion, im Gegensatz zu der Rekursion die Sie zuvor verwendet haben, können interpreter/compiler zu leeren Kontext, wenn Sie mit dem nächsten Schritt der Rekursion. Also nehmen wir an, Sie berechnen factorial(1000) Ihre version beibehalten wird 1000 Kontexten, während mir nur pflegen 1. Das bedeutet, dass Ihre version wird schließlich die Berechnung nicht das gewünschte Ergebnis, sondern nur crash auf einer Out of call stack memory Fehler.

Können Sie Lesen Sie mehr über ihn auf wikipedia.

Das Ziel factorial(0,0) sollte fail---es funktioniert nicht.

InformationsquelleAutor m09
7

Einen Recht einfachen Weg, es zu tun, ist dies:
```
fac(0,1).
fac(N,F):-
    N>0,N1 is N-1,fac(N1,F1),F is N*F1.
```
Diese Antwort gekennzeichnet wurde (da keine Antwort) für die niedrige Qualität der Warteschlange. Antworten umfasste vollständig von code sind in der Regel von oben herab angesehen, denn Sie bieten wenig Kontext/Hilfe für zukünftige Leser. So wie es aussieht, ist diese Antwort wahrscheinlich gelöscht werden, es sei denn, Sie fügen Sie ein wenig mehr detail.
Könnten Sie bitte Bearbeiten Ihre Antwort eine Erklärung zu geben, warum dieser code beantwortet die Frage? Code-nur die Antworten sind entmutigt, weil Sie nicht lehren, die Lösung.

InformationsquelleAutor Mohamed Hassan
5

Generell @m09 Antwort ist im Grunde Recht über die Wichtigkeit des tail-Rekursion.

Für große N Berechnung des Produkt anders gewinnt! Denke "binären Baum", nicht "lineare Liste"...

Lassen Sie uns versuchen, beide Möglichkeiten und vergleichen Sie die Laufzeiten. Zuerst @m09 s factorial/2:
```
?- Zeit((factorial(100000,_),false)). 
% 200,004 Rückschlüsse 1.606 CPU in 1.606 Sekunden (100% CPU, 124513 Lippen) 
falsch. 
```
Nächsten, wir tun es, Baum-Stil—mit meta-Prädikat reduzieren/3 zusammen mit lambda-Ausdrücke:
```
?- Zeit((numlist(1,100000,Xs),reduzieren(\X^Y^XY^(XY-X*Y),Xs,_),false)). 
% 1,300,042 Rückschlüsse 0.264 CPU in 0.264 Sekunden (100% CPU, 4922402 Lippen) 
falsch. 
```
Letzten, lassen Sie uns definieren, und verwenden Sie dedizierte Hilfs-Prädikat x_y_product/3:
```
x_y_product(X, Y, XY) :- XY is X*Y.
```
Was zu gewinnen? Lassen Sie uns Fragen Sie die Stoppuhr!
```
?- Zeit((numlist(1,100000,Xs),reduzieren(x_y_product,Xs,_),false)). 
% 500,050 Rückschlüsse 0.094 CPU in 0.094 Sekunden (100% CPU, 5325635 Lippen) 
falsch. 
```
InformationsquelleAutor repeat
2
```
factorial(1, 1).
factorial(N, Result) :- M is N - 1,
factorial(M, NextResult), Result is NextResult * N.
```
Sollten Sie eine Erklärung auf deine Antwort. Code-only-posts sind nicht genug. Lesen Sie hier über die details.

InformationsquelleAutor Salma
2

Normalfall erklärt wird. Die Bedingungen, die N muss positiv sein, und multiplizieren mit dem vorherigen Begriff.
```
 factorial(0, 1).
 factorial(N, F) :- 
       N > 0, 
       Prev is N -1, 
       factorial(Prev, R), 
       F is R * N.
```
Ausführen:

factorial(-1,X).

InformationsquelleAutor Shashank Motepalli

Einen einfachen Weg :

 factorial(N, F):- N<2, F=1.

 factorial(N, F) :- 
     M is N-1, 
     factorial(M,T), 
     F is N*T.

InformationsquelleAutor rashedcs

-1

Ich würde so etwas machen:
```
fact(0, 1).
fact(N, Result):-
    Next is N - 1,
    fact(Next, Recursion),
    Result is N * Recursion.
```
- Und eine tail-version wäre wie:
```
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).
```
So für Sie zu rufen:

nicht-tail-rekursive Methode: Tatsache, (3, Ergebnis).

tail-rekursive Methode: tail_fact(3, 1, Ergebnis).

Dies könnte helfen 😉

?- fact(0,1), false. nicht kündigen. Es sein sollte. Gleiche für ?- tail_fact(0,1,0), false.
Ihr Recht! fact(0,0). fact(N, R):- fact_aux(N, R). fact_aux(0, 1). fact_aux(N, R):- N > 0, NewN is N - 1, fact_aux(NewN, Rec), R is N * Rec.
Etwas besser sind. Aber ?- fact(0,0). ausfallen sollte. Gelingt es.
btw. das sieht verdächtig ähnlich zu dieser vorherigen Antwort: stackoverflow.com/a/28799827/4609915

InformationsquelleAutor João R.
-1

nicht-tailer Rekursion :
```
 fact(0,1):-!. 
   fact(X,Y):- Z=X-1,
         fact(Z,NZ),Y=NZ*X.
```
tailer Rekursion:
```
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).
```
Verwenden Sie visual-prolog?
Das Prolog-system verwenden Sie?
Mit SWI-Prolog, ?- fact(10,F). Schleifen und nicht eine Antwort geben.
ja, ich bin mit visual-prolog. @wiederholen
es wurde ein problem in die Stopp-Bedingung in visual prolog in der Ausgabe richtig, aber hört nicht nach 0, so macht stack overflow

InformationsquelleAutor Peter Osama

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.