1) basic version
{def fib1
 {lambda {:n}
  {if {< :n 3}
   then 1
   else {+ {fib1 {- :n 1}} {fib1 {- :n 2}}} }}}

{fib1 16} -> 987   (CPU ~ 16ms)
{fib1 30} = 832040 (CPU > 12000ms)

2) tail-recursive version
{def fib2
 {def fib2.r
  {lambda {:a :b :i}
   {if {< :i 1}
    then :a
    else {fib2.r :b {+ :a :b} {- :i 1}} }}}
 {lambda {:n} {fib2.r 0 1 :n}}}

{fib2 16} -> 987    (CPU ~ 1ms)
{fib2 30} -> 832040 (CPU ~2ms)
{fib2 1000} -> 4.346655768693743e+208 (CPU ~ 22ms)

3) Dijkstra Algorithm
{def fib3
 {def fib3.r
  {lambda {:a :b :p :q :count}
   {if {= :count 0}
    then :b
    else {if {= {% :count 2} 0}
    then {fib3.r :a :b
                {+ {* :p :p} {* :q :q}}
                {+ {* :q :q} {* 2 :p :q}}
                {/ :count 2}}
    else {fib3.r {+ {* :b :q} {* :a :q} {* :a :p}}
                {+ {* :b :p} {* :a :q}}
                :p :q
                {- :count 1}} }}}}
 {lambda {:n}
  {fib3.r 1 0 0 1 :n} }}

{fib3 16} -> 987    (CPU ~ 2ms)
{fib3 30} -> 832040 (CPU ~ 2ms)
{fib3 1000} -> 4.346655768693743e+208 (CPU ~ 3ms)

4) memoization
{def fib4
 {def fib4.m {array.new}}    // init an empty array
 {def fib4.r {lambda {:n}
  {if {< :n 2}
   then {array.get {array.set! {fib4.m} :n 1} :n}      // init with 1,1
   else {if {equal? {array.get {fib4.m} :n} undefined} // if not exists
   then {array.get {array.set! {fib4.m} :n
                        {+ {fib4.r {- :n 1}}
                           {fib4.r {- :n 2}}}} :n}   // compute it
   else {array.get {fib4.m} :n} }}}}                   // else get it
 {lambda {:n}
  {fib4.r :n}
  {fib4.m} }} // display the number AND all its predecessors
-> fib4
{fib4 90}
-> 4660046610375530000
[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,
317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,
165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,
20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,
1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,
72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,
2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676220,23416728348467684,
37889062373143900,61305790721611580,99194853094755490,160500643816367070,259695496911122560,420196140727489660,
679891637638612200,1100087778366101900,1779979416004714000,2880067194370816000,4660046610375530000]

5) Binet's formula (non recursive)
{def fib5
 {lambda {:n}
  {let { {:n :n} {:sqrt5 {sqrt 5}} }
   {round {/ {- {pow {/ {+ 1 :sqrt5} 2} :n}
                {pow {/ {- 1 :sqrt5} 2} :n}} :sqrt5}}} }}

{fib5 16} -> 987    (CPU ~ 1ms)
{fib5 30} -> 832040 (CPU ~ 1ms)
{fib5 1000} -> 4.346655768693743e+208 (CPU ~ 1ms)