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 :) [NEM] They also give different answers: % fibo(i) 30 514229 % ::math::fibonacci 30 832040 ---- See also [Elegance vs. performance] - [Fibonacci coding] ---- [Category Mathematics] | [Arts and crafts of Tcl-Tk programming] }