/* fib2.pl:  A vastly more efficient implementation of a Fibonacci
 * predicate.  Instead of the straight-forward recursion of fib1.pl,
 * we'll 'fake' iteration by using recursion to find the same result
 * as the previous iteration of a loop would have computed, and generate
 * the next sequence value from that result.
 *
 * Making this work requires a three-argument predicate that works behind
 * the scenes to do the dirty work.  We'll keep the predicate structure
 * from fib1.pl, but apart from handling fib(0) and fib(1),
 * it will offload the real work to the three-argument version.
 *
 * Public Form:  fib(S,V), where S is the sequence number
 * and V is the Fibonacci sequence value at position S.
 *
 * `Private' Form:  fib(S,V,Previous), where S and V are as above, and
 * Previous is the previous Fibonacci sequence value.  For example,
 * fib(7,13,8) is true -- fib(7) is 13, and the previous sequence value,
 * fib(6), is 8.  The sum of 13 and 8 is fib(8).
 *
 * As an example of how this works, consider the query fib(2,X).
 * This is turned into the call fib(2,Value,_).  The "_" is the anonymous
 * variable, used when we don't need to use that variable elsewhere.
 * The next call is fib(1,Older,Olderer), which unifies to the fib(1,1,0) fact.
 * With Older and Olderer now 1 and 0, respectively, Value is computed to be
 * 1.  Continuing back, X is known to be 1, and the query is satisfied.
 *
 * Note that this version could be shortened a little.  I left in
 * the fib(1,1) fact.  The fib(1,1,0) fact can cover for fib(1,1).
 */

fib(0,0).  % The 0th Fibonacci number is 0.
fib(1,1).  % The 1st Fibonacci number is 1.

fib(Seqnum,Value) :- Seqnum > 1,                % o.w. already handled by facts
                     fib(Seqnum, Value, _).     % _ is the anonymous variable

fib(1,1,0).                                        % need a base case fact.
fib(Seqnum,Value,Older) :- Seqnum > 1,
                           S1 is Seqnum-1,         % compute preceding seq #
                           fib(S1,Older,Olderer),  % learn seq value two back
                           Value is Older+Olderer. % sum to produce the result