// Computation of Fibonacci numbers
//
//  fibonacci(0) = 1
//  fibonacci(1) = 1
//  fibonacci(i) = fibonacci(i-1) + fibonacci(i-2) for i >= 2
var N = 10;

// Method 1: recursive function (print out a debugging message at each
// function call) (exponential algorithm with no memoization)
fun fibonacci(n) = f
{
  f = (n < 2 ? 1 : fibonacci(n-1) + fibonacci(n-2));
  @ print("fibonacci(%d) = %d\n", n, f);
}

// Evaluate fibonacci(N)
@ fibonacci(N);

// Method 2: infinite and lazy array of all Fibonacci numbers
// (linear algorithm)
var fib = [0, 1, i -> fib[i-1] + fib[i-2]];

// Print out the first N Fibonacci numbers
for (i < N) {
  @ print("fib[%d] = %d\n", i, fib[i]);
}

// Method 3: iteration over a finite array (linear algorithm)
var fib': int[N];
fib'[0] = 1;
fib'[1] = 1;
for (k < N - 2) {
  fib'[k + 2] = fib'[k + 1] + fib'[k];
  @ print("fib'[%d] = %d\n", k + 2, fib'[k + 2]);
}