Comment by iamevn
4 years ago
Wouldn't this be the recursion version with tail calls?
(define/contract (fib n)
(-> nonnegative-integer? nonnegative-integer?)
(let fib-recur ([i 1] [curr 1] [prev 0])
(cond [(= i n) curr]
[else (fib-recur (+ i 1)
(+ curr prev)
curr)])))
That's pretty much what I meant by the matrix exponentiation method - applying the map (a, b) -> (a+b, a) repeatedly. Your function definitely uses tail calls, but I was just trying to say more than tail call optimization is needed to transform the trivial recursive version
fibb 0 = 0
fibb 1 = 1
fibb n = + (fibb (- n 1)) (fibb (- n 2))
into that, or any O(n) version.