4 ms·
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 recur
by 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 agoYour 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.
- kerkeslager 9y agoI'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.
- falcor84 9y agoHere'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)
- kerkeslager 9y agoYeah, 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.
- discoursism 9y ago*in languages without tail call optimization.
- kerkeslager 9y agoIn 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.
- bitwalker 9y agoI 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.
- UncleEntity 9y agoPoked 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-generator 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...
- kerkeslager 9y agoI 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