CODEWITHSUNDEEP
recursionprologfactorial
Suhyeon CHOI
Suhyeon CHOI

Reputation: 55

Here is a problem with the factorial code that I made with Prolog

I concocted two codes to calculate the factorial with Prolog.
The first is

factorial(0, 1).
factorial(N, Result) :-
   N > 0, factorial(N - 1, Interim), Result is N * Interim.

, and the second is

factorial(0, 1).
factorial(N, Result) :-
   N > 0, M is N - 1, factorial(M, Interim), Result is N * Interim.

While the first code had a stack overflow error, the second code ran normally.

I made the following code for the test.

sum_2(N, R) :- R is N + 2.
sum_f(N, R) :- sum_2(N + 2, R).

The above code was executed normally.

I don't understand why the first code for calculating the factorial is a stack overflow error.

I'd appreciate it if you could tell me why.

Upvotes: 1

Views: 67

Answers (1)

Isabelle Newbie
Isabelle Newbie

Reputation: 9378

Are you sure that you get a stack overflow with the first version? How are you calling it? A call like factorial(5, Result) should fail, i.e., result in an answer like false or no.

Prolog doesn't "evaluate expressions" like other programming languages. A term like N - 1 is just data: A term with the functor - and two arguments N and 1. Even if N is bound to some number, say 5, the term is still just 5 - 1 and not 4. It is only mapped to 4 if you specifically ask the is predicate or one of the arithmetic comparison predicates (>, =<, =:=, etc.) to evaluate it.

So if you call your first factorial predicate as factorial(5, Result), the following things happen:

  • the goal factorial(5, Result) does not unify with factorial(0, 1), this clause is skipped
  • the goal factorial(5, Result) unifies with factorial(N, Result) with unifier N = 5, the body of this clause is executed with this binding
    • the goal 5 > 0 succeeds
    • the call factorial(5 - 1, Interim) is executed:
      • the goal factorial(5 - 1, Interim) does not unify with factorial(0, 1), this clause is skipped
      • the goal factorial(5 - 1, Interim) unifies with factorial(N, Result) with unifier N = 5 - 1 and Interim = Result, the body of this clause is executed with this binding
        • the goal 5 - 1 > 0 succeeds
        • the call factorial((5 - 1) - 1, Interim) is executed:
          • ...

This ends up calling factorial with ever larger terms 5, 5 - 1, (5 - 1) - 1, ((5 - 1) - 1) - 1, and so on. Since none of these terms ever unifies with 0, the computation can never succeed. Since each of these terms unifies with a fresh copy of N, the second clause always matches, but eventually you reach a term containing enough - 1 steps so that the goal N > 0 will fail, and the query factorial(5, Result) will fail.

Upvotes: 2

Related Questions