Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #94707

Another tail recursion example

Show all headers | View raw

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
    # https://projecteuler.net/problem=14

    import sys
    sys.setrecursionlimit(10000)

    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

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

Back to comp.lang.python | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Another tail recursion example Paul Rubin <no.email@nospam.invalid> - 2015-07-28 14:28 -0700
  Re: Another tail recursion example Paul Rubin <no.email@nospam.invalid> - 2015-07-28 14:30 -0700
  Re: Another tail recursion example Terry Reedy <tjreedy@udel.edu> - 2015-07-28 22:47 -0400

csiph-web