10 ms·

Tail Recursion Tactics: Fibonacci

102 points by desio 9y ago

tom_mellior 9y ago
Silly question: Both this post and the earlier one linked from it show that a manually written loop easily beats the tail-recursive version. That is, Go doesn't seem to do tail recursion optimization. In which case, why bother with all of this?
- phoe-krk 9y ago
  All of these versions are correct in theory, and the Go example in here is because Go is easily readable as a lingua franca. This whole post can be easily translated to other languages, including ones that do tail call optimization. Also note that, despite Go having no TCO, the author has nonetheless managed to get a huge improvement over the naïve case by using proper tail recursion.
- _ph_ 9y ago
  The tail-recursive version is a good intermediate step towards the loop version - especially if you have more complex algorithms. It would however be great, if Go would do tail call optimization, making the tail-recursive version as efficient as the explicit loop.
ArmandGrillet 9y ago
Interesting article with great formatting, I hope there will be more! Blogs like this and YouTube channels like 3Blue1Brown make maths more tangible.
- desio 9y ago
  Thank you for the feedback, I'm glad you found it interesting!
OJFord 9y ago
Great post, please add RSS for at least one subscriber!
- desio 9y ago
  I'm flattered! I added an rss feed for you: https://blog.des.io/rss.xml https://blog.des.io/rss.xml
  - agumonkey 9y ago
    Many thanks, and very very nice article. I used to spend time reading about linear recurrences and all things fibonacci. I stopped but this reminds me I should go back into it.
dwilding 9y ago
I love your explanation of how to arrive at the vector transformation function. You might enjoy reading an article I wrote a few years ago that touches on maxtrix/vector computation of linear recurrences: http://aperiodical.com/2014/06/discovering-integer-sequences-by-dealing-cards/ http://aperiodical.com/2014/06/discovering-integer-sequences... Not as detailed as your post though. Thanks for a great write up!
- desio 9y ago
  Thanks for the feedback and sharing your article. I also find the matrix solution so satisfying especially when the eignenvalues come out as the golden ratio. I would really like to do a write-up on the intuition behind this and what it means to approach a linear recurrence as a vector space, solving with a matrix and the characteristic equation.
chx 9y ago
When I see func FibTailVecSum(n int) int { if n < 2 ... and func FibTailVec(acc int, a int, b int) (int, int) { if acc == 1 { I go full Terry Pratchett and began to yell Guards! Guards! I mean, these are perfect examples of Elixir guards. Is there a similar functionality in Go?
taeric 9y ago
Would be neat to see how the vector version works using successive squares.
dustingetz 9y ago
https://wiki.haskell.org/The_Fibonacci_sequence https://wiki.haskell.org/The_Fibonacci_sequence
- moomin 9y ago
  The canonical zipWith solution is a thing of beauty.
  - cgmg 9y ago
    I agree. The scanl version is even more elegant: fibs = 0 : scanl (+) 1 fibs Replacing 0 with 2 yields the Lucas numbers: lucas = 2 : scanl (+) 1 lucas
- e12e 9y ago
  Seems to be a case of reality imitating satire: https://www.willamette.edu/~fruehr/haskell/evolution.html https://www.willamette.edu/~fruehr/haskell/evolution.html ;-) But, thanks for the pointer - from a glance it looks like a fine way to compare and contrast approaches/flavours of haskell programming.
enedil 9y ago
Unfortunate, that your results for `n = 90` are completely useless, since F_90 > 2^32 which is the size of int. Also, you could have shown a method which is O(log n), namely [[F(n+1) F(n)], [F(n) F(n-1)]] equals [[1, 1] [1, 0]] raised to the power of n.
- desio 9y ago
  Actually F_90 < 2^64. Golang ints are minimum 32bits and can be 64bits so my results were not completely useless at all ;) Indeed you can compute Fibonacci numbers (and other linear recurrences) with matrix exponentiation, or with a closed-form equation like the Binet Formula - but I limited the scope of this article to tail recursion. Binet Formula: http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.ht...
  - enedil 9y ago
    I suspect that computing Fibonacci numbers with Binet formula is slower than with matrix form - if mul(n) is the number of multiplications required to compute x^n, then matrix form will use 8 * mul(n) integer multiplications, while Binet's formula requires 2 * mul(n) floating point operations. I suspect the latter is slower.
  - Retr0spectrum 9y ago
    You can implement matrix exponentiation recursively however.
    - tmoertel 9y ago
      > You can implement matrix exponentiation recursively however. And tail recursively, and – going full circle – you can convert that tail recursion into iteration (see [1] for example, using techniques described in [2]). [1] Iterative fast-power implementation in Python https://github.com/tmoertel/practice/blob/master/libraries/tomlib.py#L143 https://github.com/tmoertel/practice/blob/master/libraries/t... [2] Recursion to Iteration, Part 1: The Simple Method, secret features, and accumulators http://blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html http://blog.moertel.com/posts/2013-05-11-recursive-to-iterat...
kerkeslager 9y ago
Tail call optimization is a clever, but even in functional languages, twisting your code around to use tail calls is often a code smell. Most uses of tail recursion would be better-served by using some higher-order functions. The reason is that when you write something tail recursively, it's sort of like rolling your own iteration. This is particularly true because many platforms don't supply tail call optimization, but do supply higher-order function. For example, Python 3: import functools import itertools def fib(n): def get_next(i): a, b = i return (b, a + b) a, b = functools.reduce( get_next, itertools.repeat(None, n), (0, 1), ) return b This does come out a bit hacky in Python, because Python doesn't have a builtin higher-order function that does something like this: def generate(get_next, c): while True: yield c c = get_next(c) But many (most?) functional languages have such a function. With that function built in, the code would look something like: import itertools def fib(n): def get_next(i): a, b = i return (b, a + b) a, b = next(itertools.islice( generate(get_next, (0, 1)), n, )) return b Further, most functional languages have a builtin function that gets the nth item in the sequence, which is what `next` and `itertools.islice` are doing above: def nth(seq, n): return next(itertools.islice(seq, n)) If that were built in also, we get: def fib(n): def get_next(i): a, b = i return (b, a + b) a, b = nth(generate(get_next, (0, 1)), n) return b This gives us some pretty terse code built only of composable builtin pieces, and ostensibly these higher-order functions are written in a lower-level language and highly optimized. This is cleaner than rolling your own tail recursion in a lot of ways.
- sillysaurus3 9y ago
  Your examples seem neither clear nor concise though. If I had to try to understand what was happening there without any comments or any understanding what "fib" was, I'd probably have to stare at that and step through it in my head. Compare that to this: https://imgur.com/a/80qlG https://imgur.com/a/80qlG Or this: https://imgur.com/a/yZNQr https://imgur.com/a/yZNQr Both are extremely easy to understand, and would remain understandable even for a new programmer. So without clarity or conciseness, what's left? Why write code using higher order functions by default? There's no win.
cousin_it 9y ago
If you're computing Fibonacci numbers using only addition, no matter how clever your recursion, you will always lose out to algorithms that use multiplication. https://www.nayuki.io/page/fast-fibonacci-algorithms https://www.nayuki.io/page/fast-fibonacci-algorithms
- engnr567 9y ago
  Exactly. And fibonacci numbers also have a closed form which can be (in theory) evaluated in O(1): http://austinrochford.com/posts/2013-11-01-generating-functions-and-fibonacci-numbers.html http://austinrochford.com/posts/2013-11-01-generating-functi...
  - cousin_it 9y ago
    The number of digits in the nth Fibonacci number grows linearly with n, so you can't compute these digits in O(1). The fastest algorithms, described in the link I gave, have complexity O(n * something) where "something" grows much slower than n and depends on the bigint multiplication algorithm used.
    - engnr567 9y ago
      The matrix exponentiation algorithm in the link you sent is O(log(n)). Yes, this might seem strange because the output (F_n) itself has n bits. But in practice most of the implementations would use long integers for output, so log(F_n) < 64 for these implementations.
      - cousin_it 9y ago
        The article I linked has code examples in four languages, all use bigints, not longs.
- e12e 9y ago
  How do you implement multiplication without addition?

102 points by desio 9y ago

Silly question: Both this post and the earlier one linked from it show that a manually written loop easily beats the tail-recursive version. That is, Go doesn't seem to do tail recursion optimization. In which case, why bother with all of this?

phoe-krk 9y ago
All of these versions are correct in theory, and the Go example in here is because Go is easily readable as a lingua franca. This whole post can be easily translated to other languages, including ones that do tail call optimization. Also note that, despite Go having no TCO, the author has nonetheless managed to get a huge improvement over the naïve case by using proper tail recursion.
_ph_ 9y ago
The tail-recursive version is a good intermediate step towards the loop version - especially if you have more complex algorithms. It would however be great, if Go would do tail call optimization, making the tail-recursive version as efficient as the explicit loop.

ArmandGrillet 9y ago

Interesting article with great formatting, I hope there will be more! Blogs like this and YouTube channels like 3Blue1Brown make maths more tangible.

desio 9y ago
Thank you for the feedback, I'm glad you found it interesting!

OJFord 9y ago

Great post, please add RSS for at least one subscriber!

desio 9y ago
I'm flattered! I added an rss feed for you: https://blog.des.io/rss.xml https://blog.des.io/rss.xml
- agumonkey 9y ago
  Many thanks, and very very nice article. I used to spend time reading about linear recurrences and all things fibonacci. I stopped but this reminds me I should go back into it.

dwilding 9y ago

I love your explanation of how to arrive at the vector transformation function. You might enjoy reading an article I wrote a few years ago that touches on maxtrix/vector computation of linear recurrences: http://aperiodical.com/2014/06/discovering-integer-sequences-by-dealing-cards/ http://aperiodical.com/2014/06/discovering-integer-sequences... Not as detailed as your post though. Thanks for a great write up!

desio 9y ago
Thanks for the feedback and sharing your article. I also find the matrix solution so satisfying especially when the eignenvalues come out as the golden ratio. I would really like to do a write-up on the intuition behind this and what it means to approach a linear recurrence as a vector space, solving with a matrix and the characteristic equation.

chx 9y ago

When I see func FibTailVecSum(n int) int { if n < 2 ... and func FibTailVec(acc int, a int, b int) (int, int) { if acc == 1 { I go full Terry Pratchett and began to yell Guards! Guards! I mean, these are perfect examples of Elixir guards. Is there a similar functionality in Go?

taeric 9y ago

Would be neat to see how the vector version works using successive squares.

dustingetz 9y ago

https://wiki.haskell.org/The_Fibonacci_sequence https://wiki.haskell.org/The_Fibonacci_sequence

moomin 9y ago
The canonical zipWith solution is a thing of beauty.
- cgmg 9y ago
  I agree. The scanl version is even more elegant: fibs = 0 : scanl (+) 1 fibs Replacing 0 with 2 yields the Lucas numbers: lucas = 2 : scanl (+) 1 lucas
e12e 9y ago
Seems to be a case of reality imitating satire: https://www.willamette.edu/~fruehr/haskell/evolution.html https://www.willamette.edu/~fruehr/haskell/evolution.html ;-) But, thanks for the pointer - from a glance it looks like a fine way to compare and contrast approaches/flavours of haskell programming.

enedil 9y ago

Unfortunate, that your results for `n = 90` are completely useless, since F_90 > 2^32 which is the size of int. Also, you could have shown a method which is O(log n), namely [[F(n+1) F(n)], [F(n) F(n-1)]] equals [[1, 1] [1, 0]] raised to the power of n.

desio 9y ago
Actually F_90 < 2^64. Golang ints are minimum 32bits and can be 64bits so my results were not completely useless at all ;) Indeed you can compute Fibonacci numbers (and other linear recurrences) with matrix exponentiation, or with a closed-form equation like the Binet Formula - but I limited the scope of this article to tail recursion. Binet Formula: http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.ht...
- enedil 9y ago
  I suspect that computing Fibonacci numbers with Binet formula is slower than with matrix form - if mul(n) is the number of multiplications required to compute x^n, then matrix form will use 8 * mul(n) integer multiplications, while Binet's formula requires 2 * mul(n) floating point operations. I suspect the latter is slower.
- Retr0spectrum 9y ago
  You can implement matrix exponentiation recursively however.
  - tmoertel 9y ago
    > You can implement matrix exponentiation recursively however. And tail recursively, and – going full circle – you can convert that tail recursion into iteration (see [1] for example, using techniques described in [2]). [1] Iterative fast-power implementation in Python https://github.com/tmoertel/practice/blob/master/libraries/tomlib.py#L143 https://github.com/tmoertel/practice/blob/master/libraries/t... [2] Recursion to Iteration, Part 1: The Simple Method, secret features, and accumulators http://blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html http://blog.moertel.com/posts/2013-05-11-recursive-to-iterat...

kerkeslager 9y ago

Tail call optimization is a clever, but even in functional languages, twisting your code around to use tail calls is often a code smell. Most uses of tail recursion would be better-served by using some higher-order functions. The reason is that when you write something tail recursively, it's sort of like rolling your own iteration. This is particularly true because many platforms don't supply tail call optimization, but do supply higher-order function. For example, Python 3: import functools import itertools def fib(n): def get_next(i): a, b = i return (b, a + b) a, b = functools.reduce( get_next, itertools.repeat(None, n), (0, 1), ) return b This does come out a bit hacky in Python, because Python doesn't have a builtin higher-order function that does something like this: def generate(get_next, c): while True: yield c c = get_next(c) But many (most?) functional languages have such a function. With that function built in, the code would look something like: import itertools def fib(n): def get_next(i): a, b = i return (b, a + b) a, b = next(itertools.islice( generate(get_next, (0, 1)), n, )) return b Further, most functional languages have a builtin function that gets the nth item in the sequence, which is what `next` and `itertools.islice` are doing above: def nth(seq, n): return next(itertools.islice(seq, n)) If that were built in also, we get: def fib(n): def get_next(i): a, b = i return (b, a + b) a, b = nth(generate(get_next, (0, 1)), n) return b This gives us some pretty terse code built only of composable builtin pieces, and ostensibly these higher-order functions are written in a lower-level language and highly optimized. This is cleaner than rolling your own tail recursion in a lot of ways.

sillysaurus3 9y ago
Your examples seem neither clear nor concise though. If I had to try to understand what was happening there without any comments or any understanding what "fib" was, I'd probably have to stare at that and step through it in my head. Compare that to this: https://imgur.com/a/80qlG https://imgur.com/a/80qlG Or this: https://imgur.com/a/yZNQr https://imgur.com/a/yZNQr Both are extremely easy to understand, and would remain understandable even for a new programmer. So without clarity or conciseness, what's left? Why write code using higher order functions by default? There's no win.

cousin_it 9y ago

If you're computing Fibonacci numbers using only addition, no matter how clever your recursion, you will always lose out to algorithms that use multiplication. https://www.nayuki.io/page/fast-fibonacci-algorithms https://www.nayuki.io/page/fast-fibonacci-algorithms

engnr567 9y ago
Exactly. And fibonacci numbers also have a closed form which can be (in theory) evaluated in O(1): http://austinrochford.com/posts/2013-11-01-generating-functions-and-fibonacci-numbers.html http://austinrochford.com/posts/2013-11-01-generating-functi...
- cousin_it 9y ago
  The number of digits in the nth Fibonacci number grows linearly with n, so you can't compute these digits in O(1). The fastest algorithms, described in the link I gave, have complexity O(n * something) where "something" grows much slower than n and depends on the bigint multiplication algorithm used.
  - engnr567 9y ago
    The matrix exponentiation algorithm in the link you sent is O(log(n)). Yes, this might seem strange because the output (F_n) itself has n bits. But in practice most of the implementations would use long integers for output, so log(F_n) < 64 for these implementations.
    - cousin_it 9y ago
      The article I linked has code examples in four languages, all use bigints, not longs.
e12e 9y ago
How do you implement multiplication without addition?