Tail Recursion Tactics: Fibonacci | Hacker News Reader

Tail Recursion Tactics: Fibonacci

blog.des.io

102 pointsdesio37 comments

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?

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.

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.

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...

Not as detailed as your post though. Thanks for a great write up!

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.

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

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-functi...

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.

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.

The article I linked has code examples in four languages, all use bigints, not longs.

How do you implement multiplication without addition?

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.

Poked around on the google[0]:

  def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return b

No itertools, not overly complex, no tail recursion.

If you were careful of the scoping rules something like foo(get_next(i) for i in whatever()) could be made to work without too much trouble (also without itertools) if you needed a sequence. Probably just throw a lambda in there instead of get_next and python would be happy, too lazy to work it out.

[0]http://www.koderdojo.com/blog/python-fibonacci-number-genera...

--edit--

Actually, I think this function gives the wrong result for 0 and maybe 1, just copypasta'd the code so blame them...

I think this is the correct way to do this in a Python codebase where procedural programming is the dominant paradigm, but that's not really what my previous post is about.

EDIT: Also c'mon man. This is not a problem that you need to Google. :P

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

Or this:

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.

I'm not sure on what basis you're saying that my final result is less concise--it's fewer characters than your first solution if you give the functions names which are as non-descriptive. :)

As for clarity: given the new programmers our industry is producing, maybe your first solution is easier to understand, but I am not sure that your first proposed solution is actually easier to understand if you assume less prior knowledge of programming. The problem is that we're currently educating people within a procedural paradigm rather than a functional one, so the procedural code is built with components the programmer understands. But if we educated people starting with a higher-order functions instead of for-loops (such as the approach taken in SICP), I'd guess that people would understand the higher-order function way better.

Your second solution seems to me to be the clearest and most concise solution of all (and, notably, it uses a functional paradigm). But it is exponentially inefficient--that's the entire point of the article. So I'm not sure why this is even being brought up in this context.

All that said, my recommendation would be to follow the dominant paradigm of your environment. If your codebase and language support primarily procedural proramming, write `fib()` with a `for` loop. If your codebase and language support primarily functional programming, write `fib()` with higher-order functions. There isn't really a good case for writing this using tail recursion.

EDIT: Also can we never ever post code in Imgur images again? Code is text and transforming it into an image loses all of the benefits of text.

Here's my suggested Python code for a tail-recursive implementation that carries all the state it needs in a single function:

    def fib_tail_recurse(n, i=1, cur_sum=1, prev_sum=0):
        if i >= n:
            return cur_sum
        return fib_tail_recurse(n, i+1, cur_sum+prev_sum, cur_sum)

Yeah, but...

    ~/$ python3
    Python 3.6.3 (default, Oct  4 2017, 06:09:05) 
    [GCC 4.2.1 Compatible Apple LLVM 8.0.0 (clang-800.0.42.1)] on darwin
    Type "help", "copyright", "credits" or "license" for more information.
    >>> import fib
    >>> fib.fib_tail_recurse(1000)
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
      File "/Users/kerkeslager/fib.py", line 4, in fib_tail_recurse
        return fib_tail_recurse(n, i+1, cur_sum+prev_sum, cur_sum)
      File "/Users/kerkeslager/fib.py", line 4, in fib_tail_recurse
        return fib_tail_recurse(n, i+1, cur_sum+prev_sum, cur_sum)
      File "/Users/kerkeslager/fib.py", line 4, in fib_tail_recurse
        return fib_tail_recurse(n, i+1, cur_sum+prev_sum, cur_sum)
      [Previous line repeated 994 more times]
      File "/Users/kerkeslager/fib.py", line 2, in fib_tail_recurse
        if i >= n:
    RecursionError: maximum recursion depth exceeded in comparison
    >>>

This is a perfect example of why tail recursion isn't actually very useful.

*in languages without tail call optimization.

In languages which are functionally-focused enough that tail call optimization can be relied upon, higher-order functions are usually available and a better solution. See my post higher up.

I prefer to use recursion in a lot of cases in languages with pattern matching in function heads (e.g. Erlang or Elixir), particularly when each "case" deals with the accumulated state differently, which is more often than not.

When you are doing simple maps/filters whatever, then yeah, higher order functions all the way.

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

Thank you for the feedback, I'm glad you found it interesting!

https://wiki.haskell.org/The_Fibonacci_sequence

Seems to be a case of reality imitating satire:

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.

The canonical zipWith solution is a thing of beauty.

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

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.

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.ht...

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.

You can implement matrix exponentiation recursively however.

> 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/t...

[2] Recursion to Iteration, Part 1: The Simple Method, secret features, and accumulators http://blog.moertel.com/posts/2013-05-11-recursive-to-iterat...

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

I'm flattered! I added an rss feed for you: https://blog.des.io/rss.xml

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.

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

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?

Reply on news.ycombinator.com