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
def generate(get_next, c):
while True:
yield c
c = get_next(c)
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
def nth(seq, n):
return next(itertools.islice(seq, n))
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
def fib(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return b
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...
EDIT: Also c'mon man. This is not a problem that you need to Google. :P
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:
Or this:
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.
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.
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) ~/$ 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
>>>
http://austinrochford.com/posts/2013-11-01-generating-functi...
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.
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.
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...
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.
Not as detailed as your post though. Thanks for a great write up!