Prolog無限再帰はスタックをいっぱいにしませんか？

Question

実行すると、しかし...スタックは迅速による無限再帰に埋め、次の例を

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

を、次の例を使用し、バックトラックするために要求された（使用;）、いっぱいにすることなく、同じ無限再帰を打ちますスタック...

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

は、私はどちらかの関数は末尾再帰的であると信じて、そうしない理由秒1 ない原因........... StackOverflowのでしょうか？ （yaaaaoww .... サングラス）

Answer 1

クエリが?- is_pos_integer(1)のようなもので、その後の説明は、この場合を想定して：

最初の例だけで末尾再帰の対象とならない無限ループに入ります。スタックがいっぱいになります。

2番目の例もまた、最終的には非常にゆっくりといっぱいになります。

最初の句Aと2番目の句Bにラベルを付けましょう。is_pos_integer(0)の最初のバージョンを呼び出すと、コールパターンはAAAAA ...（スタック不足）です。 2番目のバージョンを呼び出すと、Aが返されます（これはトップレベルにtrueに戻ります）。その後、0が0 + 1と等しくないために失敗するバックトラックBAに続いて、0が1 + 1などと等しくないために再度失敗するBBAあなたはBBの呼び出しを受け取ります... B（ntimes）し、Aが失敗します。最終的にスタックが使い果たされますが、非常に長い時間がかかります。