tail recursion

[4meta5]

calculate sequences upwards instead of downward

fib(0,0).
fib(1,1).
fib(2,1).
fib(N,R) :-
    N1 is N-1,
    N2 is N-2,
    fib(N1,R1),
    fib(N2,R2),
    R is R1 + R2.

to

fib2(N,R) :-
    fib2(2,N,1,1,R).
fib2(X,N,_,F2,F2) :-
    X >= N.
fib2(X,N,F1,F2,R) :-
    X < N,
    X1 is X+1,
    F3 is F1+F2,
    fib2(X1,N,F2,F3,R).

TODO

• [x] fibonacci
• [x] factorial
• [x] derangement

last attempt fucked up the initial conditions

derg(N,R) :-
    derg(1,N,1,0,R).
derg(_,1,_,R,R).
derg(_,0,R,_,R).
derg(X,N,_,R,R) :-
    X>=N.
derg(X,N,D1,D2,R) :-
    X<N,
    X1 is X+1,
    D3 is (N-1)*(D1+D2),
    derg(X1,N,D2,D3,R).

[4meta5]

derangement is close, but fails on 4 (yields 12 instead of 9 for some reason)

?- derg(0,R).
false.

?- derg(1,R).
R = 0 .

?- derg(2,R).
R = 1 .

?- derg(3,R).
R = 2 .

?- derg(4,R).
R = 12 .

?- der(4,R).
R = 9 .

code:

derg(N,R) :-
    derg(2,N,0,1,R).
derg(X,N,R,_,R) :- X is N+1.
derg(X,N,_,R,R) :- X=N.
derg(X,N,D1,D2,R) :-
    X<N,
    N1 is N-1,
    X1 is X+1,
    D3 is (N1 * (D1 + D2)),
    derg(X1,N,D2,D3,R).

[4meta5]

done

der(N,R) :-
    der(2,N,0,1,R).
der(X,N,R,_,R) :- X is N+1.
der(X,N,_,R,R) :- X=N.
der(X,N,D1,D2,R) :-
    X<N,
    X1 is X+1,
    D3 is (X * (D1 + D2)),
    der(X1,N,D2,D3,R).