3 ms·
Wouldn't this be the recursion version with tail calls? (define/contract (fib n) (-> nonnegative-integer? nonnegative-integer?) (let fib-recur ([i 1]
by iamevn 6y 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)])))
- desertrider12 6y agoThat'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.