(original) (raw)

#!/usr/bin/env setl -- -- Fibonacci sequence in SETL. -- -- See -- * http://en.wikipedia.org/wiki/Fibonacci\_chain -- * http://mathworld.wolfram.com/FibonacciNumber.html -- -- From http://rosettacode.org/wiki/Fibonacci\_sequence -- """ -- Write a function to generate the nth Fibonacci number. Solutions can be -- iterative or recursive (though recursive solutions are generally considered -- too slow and are mostly used as an exercise in recursion). Support for -- negative n is optional. -- """ -- -- This SETL program was created by Hakan Kjellerstrand (hakank@bonetmail.com) -- Also see my SETL page: http://www.hakank.org/setl/ -- n:= 100; print("fib(",n,"):", fib(n)); print("fib_array(",n,"):",fib_array(n)); print("fib_array2(",n,"):",fib_array2(n)); print("fib_rec(10):", fib_rec(10)); -- slow print("fib_rec_cache(100):", fib_rec_cache(100)); -- fast -- -- recursive: slow -- proc fib_rec(n); if n <= 2 then return 1; else return fib_rec(n-1) + fib_rec(n-2); end if; end proc; -- -- recursive with cache. Fast. -- proc fib_rec_cache(n) ; cache := {[1,1],[2,1]}; f:=fib_rec_cache1(n,cache); return f; end proc; proc fib_rec_cache1(n,rw cache); if cache(n) /= om then return cache(n); end if; if n <= 2 then return 1; end if; f1 := fib_rec_cache1(n-1, cache); cache(n-1) := f1; f2 := fib_rec_cache1(n-2, cache); cache(n-2) := f2; return f1 + f2; end proc; -- -- Iterative solution -- proc fib(n); f1 := 1; f2 := 1; ix := 2; while ix < n loop tmp := f1; f1 := f2; f2 := tmp + f1; ix +:= 1; end loop; return f2; end proc; -- -- collect in an array -- proc fib_array(n); f1 := 1; f2 := 1; f := [f1,f2]; ix := 2; while ix < n loop tmp := f1; f1 := f2; f2 := tmp + f1; f with:= f2; ix +:= 1; end loop; return f; end proc; -- -- array (tuple) comprehension -- proc fib_array2(n); s:= [1,1]; f:= s; return s + [f(i) := f(i-1)+f(i-2) : i in [3..n]]; end proc;