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.
--
https://mail.python.org/mailman/listinfo/python-list
