Prolog unendliche Rekursion nicht den Stapel füllen?

Mit dem folgenden Beispiel wird der Stapel schnell aufgrund einer unendlichen Rekursion füllt ...Prolog unendliche Rekursion nicht den Stapel füllen?

is_pos_integer(X):- is_pos_integer(Y),X is Y+1. 
is_pos_integer(0).

jedoch das folgende Beispiel bei der Ausführung und forderte einen Rückzieher (mit;), trifft die gleiche unendliche Rekursion ohne die oben Füllung Stapel ...

is_pos_integer(0). 
is_pos_integer(X):- is_pos_integer(Y),X is Y+1.

ich glaube nicht, entweder Funktion Schwanz rekursiv ist, also warum würde die zweite nicht Ursache ein ........... Stackoverflow? (Yaaaaoww .... Sonnenbrille)

Quelle

2016-10-18 Andrew

Auf welche Abfrage und welches Prolog-System? – Eyal

Ja, * weder Beispiel * ist Tail rekursiv! Und: Die Tail-Call-Optimierung gilt nur, wenn * keine Auswahlpunkte * übrig sind! Das erste Beispiel muss auch die Auswahlpunkte im Auge behalten. Noch eine elementare Anmerkung: Es ist normalerweise viel besser, positive Ganzzahlen mit den ** CLP (FD) ** - Einschränkungen Ihres Prolog-Systems zu beschreiben, zum Beispiel: 'positive_integer (I): - I #> 0.' – mat

Unter der Annahme, dass Ihre Abfrage so etwas wie ?- is_pos_integer(1) ist, dann ist die Erklärung dazu:

Das erste Beispiel geht nur in eine Endlosschleife nicht unter Schwanz-Rekursion. Also füllt sich der Stapel.

Das zweite Beispiel füllt sich schließlich, aber sehr langsam.

Beschriften wir die erste Klausel A und zweite Klausel B. Wenn Sie die erste Version von is_pos_integer(0) aufrufen, ist das Aufrufmuster AAAAA ... (out of stack). Wenn Sie die zweite Version aufrufen, erhalten Sie A (das auf true auf die oberste Ebene zurückkehrt) und dann Backtracking BA, das fehlschlägt, weil 0 ungleich 0 + 1 ist, dann BBA, die erneut fehlschlägt, weil 0 nicht gleich 1 + 1 ist Du erhältst einen Anruf von BB ... B (n) und dann A, was fehlschlägt. Irgendwann wird dir der Stapel ausgehen, aber das wird sehr lange dauern.

Quelle

2016-10-19 02:34:02 Eyal

Prolog unendliche Rekursion nicht den Stapel füllen?

Antwort

Verwandte Themen