[Fib in TAL] ,by [kbk] ,2012-08-21 [Fibonacci Numbers With the U Combinator] ,by [kbk] ,2012-08-21 [http://paste.tclers.tk/2683%|%two implementations of fib%|%] ,[kbk] ,2012-08-21 [Fibonacci numbers with coroutine], 2015-11-12 [Richard Suchenwirth] 2005-04-06 - Fibonacci numbers [http://mathworld.wolfram.com/FibonacciNumber.html] are a famous example for recursion. They are defined as ======none 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}"} ====== However, on moderate arguments it gets immoderately slow: ======none % 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]]} } ====== 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>0} {incr x -1} { set tmp $last incr last $prev set prev $tmp } set prev } ====== 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 } } ====== 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): ======none % 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 ''([RS]: Oops - fixed in fibo(i))'': ======none % fibo(i) 30 514229 % ::math::fibonacci 30 832040 ====== You can also generalise the (tcllib) proc to generate the similar Lucas numbers too: ====== proc Fibish {first second n} { if {$n == 0} { return $first } else { for {set i 1} {$i < $n} {incr i} { set tmp $second incr second $first set first $tmp } return $second } } interp alias {} Fib {} Fibish 0 1 interp alias {} Lucas {} Fibish 2 1 ====== This appears to be identical in speed to the tcllib version (which it is just a slight generalisation of). ======none % proc showfirst {f n} { set ret [list] for {set i 0} {$i <= $n} {incr i} { lappend ret [$f $i] } return $ret } % showfirst Fib 30 0 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 % showfirst Lucas 30 2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 2207 3571 5778 9349 15127 24476 39603 64079 103682 167761 271443 439204 710647 1149851 1860498 ====== ---- [KPV] If speed is the goal then forget the iterative approach and just compute the value directly using the formula: ======none F(i) = round(phi**i / sqrt(5)) ====== ====== proc Fib2 {n} { set r5 [expr {sqrt(5)}] set phi [expr {(1 + $r5) / 2}] return [expr {round(pow($phi, $n)/ $r5)}] } ====== On my 700Mhz XP machine I get: ======none % time {Fib2 46} 5000 10 microseconds per iteration % time {::math::fibonacci 46} 5000 74 microseconds per iteration % time {fibo(i) 46} 5000 81 microseconds per iteration ====== [MPJ]: Using the above code and making it just one call to [expr] I was able to shave a microsecond or two. ====== proc Fib3 {n} { return [expr {round(pow(((1 + sqrt(5)) / 2), $n)/ sqrt(5))}] } ====== [NEM]: And in-lining as much as possible yields: ====== proc Fib4 n { expr {round(pow(1.61803398875,$n)/2.2360679775)} } ====== which takes just 12 microseconds to compute Fib4 30 on my 800MHz G4 (compared to 21 µs for Fib3). ---- Toni: This example, taken from a javascript source is very much much faster. ====== proc fibo {x} { if {$x<2} { return [list 0 1] } else { set l [fibo [expr $x-1]] set len [llength $l] lappend l [expr [lindex $l [expr $len-1]]+[lindex $l [expr $len-2]]] return $l } } ====== ---- See also [Elegance vs. performance] - [Fibonacci coding] <> Mathematics | Arts and crafts of Tcl-Tk programming