if 0 {[Richard Suchenwirth] 2005-04-06 - Fibonacci numbers
(http://mathworld.wolfram.com/FibonacciNumber.html) are a famous
example for recursion. They are defined as
   fib(0) = 0
   fib(1) = 1
   fib(x) = fib(x-1) + fib(x-2)
As in all non-trivial cases it calls itself twice, [tail call optimization] (there's also Fibonacci code on that page)
is not helping here. The straightforward implementation is very simple:}
 proc fibo(r) x {
    expr {$x<2? $x: [fibo(r) [- $x 1]] + [fibo(r) [- $x 2]]}
 }
# where [expr] operators are exposed as commands (not needed in [Jim]):
 foreach op {+ -} {proc $op {a b} "expr {\$a $op \$b}"}
if 0 {However, on moderate arguments it gets immoderately slow:
 % time {fibo(r) 30} 1
 168360042 microseconds per iteration
Trying to get faster by using [incr] - it changes ''x'', so the
second time we again de-increment by 1:}
 proc fibo(r2) x {
    expr {$x<2? $x: [fibo(r2) [incr x -1]] + [fibo(r2) [incr x -1]]}
 }
if 0 {But 93 seconds are still long:
 % time {fibo(r2) 30} 1
 93862895 microseconds per iteration
Iterative solutions (which avoid recursion) are expected to be much
faster, and the art of [tail call optimization] is to convert elegant recursions
into efficient iterations.

The iterative version I cooked up is more "imperative" and complex.
The [for] loop looks a bit
funny, because it initializes all but the "loop variable", but we use
the single argument for that, and decrement it:}
 proc fibo(i) x {
    if {$x < 2} {return $x}
    for {set last 1; set prev 0} {$x>1} {incr x -1} {
        set  tmp  $last
        incr last $prev
        set  prev $tmp
    }
    set prev
 }
if 0 {Just for comparison, here's the iterative solution from [Tcllib]:}
 namespace eval math {} ;# to be independent of Tcllib itself...
 
 proc ::math::fibonacci {n} {
    if { $n == 0 } {
 	   return 0
    } else {
       set prev0 0
       set prev1 1
       for {set i 1} {$i < $n} {incr i} {
           set tmp $prev1
           incr prev1 $prev0
           set prev0 $tmp
       }
       return $prev1
    }
 }
if 0 {To my surprise, although it's lengthier, ''math::fibonacci'' runs
still 5% faster than ''fibo(i)'' - tested again on on fib(30), which results
in 514229 from all candidates (on my 200MHz Win95 box at home):
 % time {math::fibonacci 30} 5000
 255 microseconds per iteration
 % time {fibo(i) 30} 5000
 268 microseconds per iteration

Could it be that initialization in the
[for] loop creates less efficient bytecode than if it's done outside it?
But in any case, it's good to know that [Tcllib] users get the fastest version :)
----
See also [Elegance vs. performance] - [Fibonacci coding]
----
[Category Mathematics] | [Arts and crafts of Tcl-Tk programming]
}