Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Tail Recursion Tactics: Fibonacci

blog.des.io

Post reply on HN
Print view View original

21–30 of 38 posts

Re: Tail Recursion Tactics: Fibonacci

#21

Post by sillysaurus3 »

kerkeslager wrote: post #19

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,…

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.

Re: Tail Recursion Tactics: Fibonacci

#23

Post by falcor84 »

kerkeslager wrote: post #19

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,…

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)

Re: Tail Recursion Tactics: Fibonacci

#24

Post by kerkeslager »

falcor84 wrote: post #23
kerkeslager wrote: post #19

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,…

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 "", line 1, in 
      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.

Re: Tail Recursion Tactics: Fibonacci

#25

Post by discoursism »

kerkeslager wrote: post #24
falcor84 wrote: post #23

Earlier quoted context omitted.

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 " ", line 1, in File "/Users/kerkeslager/fib.py", line 4, in fib_tail_recurse return fib_tail_recurse(n, i+1, cur_sum+prev_s…

*in languages without tail call optimization.

Re: Tail Recursion Tactics: Fibonacci

#26

Post by cgmg »

moomin wrote: post #16
dustingetz wrote: post #13

https://wiki.haskell.org/The_Fibonacci_sequence

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

Re: Tail Recursion Tactics: Fibonacci

#27

Post by kerkeslager »

sillysaurus3 wrote: post #21
kerkeslager wrote: post #19

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,…

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 wit…

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.

Re: Tail Recursion Tactics: Fibonacci

#28

Post by kerkeslager »

discoursism wrote: post #25
kerkeslager wrote: post #24

Earlier quoted context omitted.

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 " ", line 1, in File "/Users/kerkeslager/fib.py", line 4, in fib_tail_recurse return fib_tail_recurse(n, i+1, cur_sum+prev_s…

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

Re: Tail Recursion Tactics: Fibonacci

#29

Post by bitwalker »

kerkeslager wrote: post #28
discoursism wrote: post #25

Earlier quoted context omitted.

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

Re: Tail Recursion Tactics: Fibonacci

#30

Post by engnr567 »

cousin_it wrote: post #22

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

Post reply on HN