CODEWITHSUNDEEP
recursionprologclpfdprolog-cut
Sergey
Sergey

Reputation: 11928

Prolog recursion overflow

fact(1,1):-!.
fact(N,F):-
    N1=N-1,
    fact(N1,F1),
    F=F1*N.

It leads to the stackoverflow(not the site)! It shouldn't because of the cut(!). Does it work in SWI-Prolog?

Upvotes: 1

Views: 238

Answers (1)

false
false

Reputation: 10142

Please note that both definitions (the OP's and pad's) do not terminate for a query like fact(0,N). But also fact(1,2) does not terminate. It should fail. And for fact(N, F) it gives only one correct answer, but there should be infinitely many. Using cuts for such purpose is very tricky. The cleanest way to fix this is to add the goal N > 0 to the rule and have a fact fact(0,1). There is an even better way, provided you use SWI-Prolog: Use library(clpfd). In the documentation, you find n_factorial/2 already defined. It can be used for queries like:

?- n_factorial(47, F).
   F = 258623241511168180642964355153611979969197632389120000000000
;  false.
?- n_factorial(N, 1).
   N = 0
;  N = 1
;  false.
?- n_factorial(N, 3).
   false.

Upvotes: 4

Related Questions