fib.prolog

fib(0, 0).
fib(1, 1).
fib(X, Y1 + Y2) :- fib(X - 1, Y1), fib(X - 2, Y2).
%% これだと X - 1 がいつまでも簡約（？）
%% されずに停まらなくなるのどうして？
% {trace}
% | ?- fib(2, What).
% 1  1 Call: fib(2,_279) ?
% 2  2 Call: fib(2-1,_311) ?
% 3  3 Call: fib(2-1-1,_341) ?
% 4  4 Call: fib(2-1-1-1,_371) ?
% ...

fib(0, 0).
fib(1, 1).
fib(X, Y) :-
    X1 is X - 1, fib(X1, Y1),
    X2 is X - 2, fib(X2, Y2),
    Y is Y1 + Y2.
%% こうやっていちいち is 使うと停まる
% {trace}
% | ?- fib(2, What).
% 1  1  Call: fib(2,_279) ?
% 2  2  Call: _351 is 2-1 ?
% 2  2  Exit: 1 is 2-1 ?
% 3  2  Call: fib(1,_376) ?
% 3  2  Exit: fib(1,1) ?
% 4  2  Call: _404 is 2-2 ?
% 4  2  Exit: 0 is 2-2 ?
% 5  2  Call: fib(0,_429) ?
% 5  2  Exit: fib(0,1) ?
% 6  2  Call: _279 is 1+1 ?
% 6  2  Exit: 2 is 1+1 ?
% 1  1  Exit: fib(2,2) ?
% What = 2 ?