declare fun {Fib N} %% Assume: N >= 0 if N == 0 then 1 else {FibHelper N 1 1 1} end end % Design of the helper is done by making the following table for {Fib 5}, % after observing that the next Fib number is the previous (FibWherem1) % plus this one (FibWhere), if one starts making a table from the beginning. % % Sought Where FibWhere FibWherem1 % 5 1 1 1 % 5 2 2 1 % 5 3 3 2 % 5 4 5 3 % 5 5 8 5 % So, at each step, Where is incremented, FibWherem1 becomes FibWhere, % and FibWhere becomes FibWhere+FibWherem1. % % We stop when Where == Sought. fun {FibHelper Sought Where FibWhere FibWherem1} % Assume: N >= 1 if Where == Sought then FibWhere else {FibHelper Sought Where+1 FibWhere+FibWherem1 FibWhere} end end