Writing a factorial-like function (Prolog)

1
votes

I have to write a Prolog program to compute:

  f(0) = 2, 
  f(1) = 0,  
  f(2) = 3,
  f(n) = 3f(n-3) + 2f(n-2) - f(n-1) for n≥3.

I need to make an iterative version, as well as a recursive version. I was able to write that recursive version in SML:

fun myFunc 0 = 2
|   myFunc 1 = 0
|   myFunc 2 = 3
|   myFunc x = 3* myFunc(x-3) + 2* myFunc(x-2) - myFunc(x-1)

But am having trouble transferring it to Prolog as i'm very new to the language. Also, I was never able to figure out how to do an iterative approach. Any help would be greatly appreciated!

Here is my attempt at the Prolog recursive version. It doesn't compile and probably isn't even close to right:

my_Fun(0, 2).
my_Fun(1, 0). 
my_Fun(2, 3). 
my_Fun(X, F) :-
   X>=3, NewX is X-3, NewF is 3 * F, my_fun(NewX,NewF), 
   NewX2 is X-2, NewF2 is 2 * F, my_fun(NewX2, NewF2),
   NewX3 is X-1, NewF3 is F, myFun(NewX3,NewF3).
2
prologfactorial
first check the spelling:) you have my_Fun,myFun and my_fun. keep in mind prolog is case-sensitive. maybe reason why it won't compile - ssbarbee
Oops! Well, i'm sure there are lot's of other problems with it, too. It was more just to show my approach towards the solution. - user2796815
iterative approach: count up (not down): f(n) depends on three previous values of f, so just maintain them: step (n,a,b,c) = (n+1,b,c,3a+2b-c). - Will Ness

2 Answers

2
votes

Ok here is the correct code:) Your biggest mistake is making variables NewF,NewF2,NewF3 dependent on something that doesn't have value yet (example: NewF is 3*F... we don't know F yet). Check the code below and notice the difference.`

my_fun(0, 2).
my_fun(1, 0). 
my_fun(2, 3). 
my_fun(X, F) :- X>=3, NewX is X-3,  my_fun(NewX,NewF),
                      NewX2 is X-2,  my_fun(NewX2, NewF2),
                      NewX3 is X-1,  my_fun(NewX3,NewF3),
                      F is 3*NewF+2*NewF2-NewF3.

Here is the code when using iterative approach. We use accumulators to store the values we need and then use those values to get the result.

my_fun_iterative(0,2) :- !.
my_fun_iterative(1,0) :- !.
my_fun_iterative(2,3) :- !.

my_fun_iterative(X,F) :- X > 2,
                         my_fun_iterative(0,ZeroV),
                         my_fun_iterative(1,OneV),
                         my_fun_iterative(2,TwoV),
                         V is 3*ZeroV+2*OneV-TwoV,
                         my_fun_iterative(X,3,OneV,TwoV,V,F),!.

my_fun_iterative(X,X,_,_,F,False) :- not(F=False),!,false.
my_fun_iterative(X,X,_,_,F,F).
my_fun_iterative(X,N,SecondV,ThirdV,Acc,F) :- X > 3,
                                              AccNew is 3*SecondV+2*ThirdV-Acc,
                                              NNew is N+1,
                                              my_fun_iterative(X,NNew,ThirdV,Acc,AccNew,F).
2
votes

Here's a recursive version that avoids multiple recalculations by saving the last 3 calculations on each iteration:

my_fun(N, F) :-
    my_fun(N, F, _, _).

my_fun(N, F, F2, F1) :-
    N >= 3,
    N1 is N-1,
    my_fun(N1, F2, F1, F0),
    F is 3*F0 + 2*F1 - F2.
my_fun(0, 2, 0, 0).  % 3rd and 4th terms are "dummies"
my_fun(1, 0, 2, 0).  % 4th term is "dummy"
my_fun(2, 3, 0, 2).

An example of an iterative (tail recursive) version:

my_fun_it(N, F) :-
    N >= 3,
    my_fun_it(0, F0),
    my_fun_it(1, F1),
    my_fun_it(2, F2),
    my_fun_it(N, 3, F, F2, F1, F0).
my_fun_it(0, 2).
my_fun_it(1, 0).
my_fun_it(2, 3).

my_fun_it(N, C, F, F2, F1, F0) :-
    C < N,
    my_fun_calc(F0, F1, F2, F3),
    C1 is C + 1,
    my_fun_it(N, C1, F, F3, F2, F1).
my_fun_it(N, N, F, F2, F1, F0) :-
    my_fun_calc(F0, F1, F2, F).

my_fun_calc(F0, F1, F2, F) :-
    F is 3*F0 + 2*F1 - F2.

I decided to pull the calculation into its own predicate since I didn't like the same thing in two different places.