/* 

  Fibonacci (code golf) in Picat.

  https://codegolf.stackexchange.com/questions/85/fibonacci-function-or-sequence
  """
  Fibonacci function or sequence

  The Fibonacci sequence is a sequence of numbers, where every number in the sequence 
  is the sum of the two numbers preceding it. The first two numbers in the sequence 
  are both 1. Here are the first few terms:

  1 1 2 3 5 8 13 21 34 55 89 ...

  Write the shortest code that either, in accordance to the standard sequence rules:
  * Generates the Fibonacci sequence without end.
  * Given n calculates the nth term of the sequence. (Either 1 or zero indexed)
  * Given n calculates the first n terms of the sequence

  You may use standard forms of input and output.

  For the function that takes an n, a reasonably large return value (the largest Fibonacci 
  number that fits your computer's normal word size, at a minimum) has to be supported.
  """

  This program was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

% import util.
% import cp.

main => go.

go ?=>
  [f(N):N in 0..30].println,  
  [g(N):N in 0..30].println,
  h(31).println,
  [i(N):N in 0..30].println,  
  nl.
go => true.

% 35 chars
% table % for performance
f(0)=1. f(1)=1. f(N)=f(N-1)+f(N-2).

% 30 chars
% table % for performance
g(N)=cond(N<2,1,g(N-1)+g(N-2)).

% 69 chars
h(N)=F=>F=new_array(N),F[1]=1,F[2]=1,foreach(I in 3..N)F[I]=F[I-1]+F[I-2] end.

% 49 chars
i(N)=B=>[A,B]=[1,1],foreach(_ in 1..N)T=A,A:=T+B,B:=T end.