Tail Recursion Tactics: Fibonacci
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&#x27;s sort of like rolling your own iteration.<p>This is particularly true because many platforms don&#x27;t supply tail call optimization, but do supply higher-order function.<p>For example, Python 3:<p><pre><code>    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
</code></pre>
This does come out a bit hacky in Python, because Python doesn&#x27;t have a builtin higher-order function that does something like this:<p><pre><code>    def generate(get_next, c):
        while True:
            yield c
            c = get_next(c)
</code></pre>
But many (most?) functional languages have such a function. With that function built in, the code would look something like:<p><pre><code>    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
</code></pre>
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:<p><pre><code>    def nth(seq, n):
        return next(itertools.islice(seq, n))
</code></pre>
If that were built in also, we get:<p><pre><code>    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
</code></pre>
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.