%fatorial ingênuo: fat(n) = n * fat(n-1); fat(0)=1
fatorial( 0, 1 ).
fatorial( N, F ) :-
    M is N - 1,
    fatorial( N, G ),
    F is G * N.

% ?- fatorial( 4, X ).                                                                       [N1 = 4,F1 = X]
% ?- M1 is 4 - 1, fatorial( M1, G1 ), X is G1 * 4.                                           [M1 = 3]
% ?- fatorial( 3, G1 ), X is G1 * 4.                                                         [N2 = 3, F2 = G1]
% ?- M2 is 3 - 1, fatorial( M2, G2 ), G1 is G2 * 3, X is G1 * 4.                             [M2=2]
% ?- fatorial( 2, G2 ), G1 is G2 * 3, X is G1 * 4.                                           [N3 = 2, F3=G2]
% ?- M3 is 2 - 1, fatorial( M3, G3 ), G2 is G3 * 2, G1 is G2 * 3, X is G1 * 4.               [M3=1]
% ?- fatorial( 1, G3 ), G2 is G3 * 2, G1 is G2 * 3, X is G1 * 4.                             [N4 = 1, F4 = G3]
% ?- M4 is 1 - 1, fatorial( M4, G4 ), G3 is G4 * 1, G2 is G3 * 2, G1 is G2 * 3, X is G1 * 4. [M4= 0]
% ?- fatorial( 0, G4 ), G3 is G4 * 1, G2 is G3 * 2, G1 is G2 * 3, X is G1 * 4.               [G4=1, cláusula de parada]
% ?- G3 is 1 * 1, G2 is G3 * 2, G1 is G2 * 3, X is G1 * 4. [G3=1, G3=2, G1=6, X=24]
% X=24
% fatorial smart
fat( N, F ) :- fat( N, 1, F ).

fat( 0, F, F ).
fat( N, Acc, F ) :-
    N > 0,
    N1 is N - 1,
    NovoAcc is Acc * N,
    fat( N1, NovoAcc, F ).

%?- fat(4, X)
%?- fat(4, 1, X).
%?- fat(3, 4, X).
%?- fat(2, 12, X).
%?- fat(1, 24, X).
%?- fat(0, 24, X). ---> X=24



% Implementa a definição oficial de Fibonacci.
% Como em outras linguagen, esta definição leva a
% implementações ineficientes.
% fib(1) = 1
% fib(2) = 1
% fib(n) = fib(n-1) + fib(n-2), n > 2
fiburro( 1, 1 ).
fiburro( 2, 1 ).
fiburro( N, F ) :-
    N > 2,
    N1 is N - 1,
    N2 is N - 2,
    fiburro( N1, F1 ),
    fiburro( N2, F2 ),
    F is F1 + F2.

%Fibonacci esperto: dois argumentos extras armazenando fib(n-1) e fib(n-2)
fibonacci( N, F ) :-  
    fib( N, 1, 1, F ).

fib( 1, _, F, F ).
fib( 2, F, _, F ).
fib( N, FibNmenos1, FibNmenos2, F ) :-
    N > 2,
    N1 is N-1,
    Fib is FibNmenos1 + FibNmenos2,
    fib( N1, Fib, FibNmenos1, F ).

% ?- fibonacci(4, X).
% ?- fib(4, 1, 1, X ).
% ?- fib(3, 2, 1, X ).
% ?- fib(2, 3, 2, X ).  --> X = 3


% Exercícios:
% 1- soma_lista(Xs, S): Xs = [X1, ..., Xn] , S = X1 + ... + Xn
% 2- produtoria(Xs, P):  Xs = [X1, ..., Xn], P = X1 * ... * Xn.