Another tail recursion example

Paul Rubin at nospam.invalid
Tue Jul 28 23:28:55 CEST 2015

Chris Angelico was asking for examples of tail recursion that didn't
have obvious looping equivalents.  Here's an Euler problem solution
using memoization and (except that Python doesn't implement it) tail
recursion with an accumulator.

    # Solution to Euler problem 14, using memoization

    import sys

    def memoize(func):
        def mf(n, a, func=func, memo={}):
            if n in memo: return memo[n]+a
            return memo.setdefault(n,func(n,0))+a
        return mf

    def col(n, a):
        if n==1: return a
        if n%2==0: return col(n//2, 1+a)
        return col(3*n+1, 1+a)

    def main():
        print max((col(i,0),i) for i in xrange(1,1000001))

If I have it right, this should result in fewer calls to the col (short
for Collatz) function than turning it into the obvious explicit loop.
To get the same gain you'd have to thread the memoization through the
function in a probably ugly way.  It's certainly doable, but as the
saying goes, why trouble your beautiful mind over something like that.
The above solution seems pretty natural to me.

More information about the Python-list mailing list