How to change this tree-recursion to a tail-recursion?

Question

I am writing a function ChrNumber that converts Arab number string to Chinese financial number string. I work out a tree recursion form. But when I tried to get a tail-recursion form, it is really difficult for me to handle the situation bit equals 6,7 or 8 or 10 and bigger ones.

You can see how it works at the end of my question.

Here's the tree-recursion solution. It works:

# -*- coding:utf-8 -*-

unitArab=(2,3,4,5,9)
#unitStr=u'十百千万亿' #this is an alternative
unitStr=u'拾佰仟万亿'
unitDic=dict(zip(unitArab,(list(unitStr))))
numArab=list(u'0123456789')
#numStr=u'零一二三四五六七八九' #this is an alternative
numStr=u'零壹贰叁肆伍陆柒捌玖'
numDic=dict(zip(numArab,list(numStr)))
def ChnNumber(s):
    def wrapper(v):
        'this is to adapt the string to a abbreviation'
        if u'零零' in v:
            return wrapper(v.replace(u'零零',u'零'))
        return v[:-1] if v[-1]==u'零' else v
    def recur(s,bit):
        'receives the number sting and its length'
        if bit==1:
            return numDic[s]
        if s[0]==u'0':
            return wrapper(u'%s%s' % (u'零',recur(s[1:],bit-1)))
        if bit<6 or bit==9:
            return wrapper(u'%s%s%s' % (numDic[s[0]],unitDic[bit],recur(s[1:],bit-1)))
        'below is the hard part to be converted to tail-recurion'
        if bit<9:
            return u'%s%s%s' % (recur(s[:-4],bit-4),u"万",recur(s[-4:],4))
        if bit>9:
            return u'%s%s%s' % (recur(s[:-8],bit-8),u"亿",recur(s[-8:],8))
    return recur(s,len(s))

My attempt version is only in recur function, I use a closure res and move the bit inside the recur so there is less arguments.:

res=[]
def recur(s):
    bit=len(s)
    print s,bit,res
    if bit==0:
        return ''.join(res)
    if bit==1:
        res.append(numDic[s])
        return recur(s[1:])
    if s[0]==u'0':
        res.append(u'零')
        return recur(s[1:])
    if bit<6 or bit==9:
        res.append(u'%s%s' %(numDic[s[0]],unitDic[bit]))
        return recur(s[1:])
    if bit<9:
        #...can't work it out
    if bit>9:
        #...can't work it out

the test code is:

for i in range(17):
    v1='9'+'0'*(i+1)
    v2='9'+'0'*i+'9'
    v3='1'*(i+2)
    print '%s->%s\n%s->%s\n%s->%s'% (v1,ChnNumber(v1),v2,ChnNumber(v2),v3,ChnNumber(v3))

which should output:

>>> 
90->玖拾
99->玖拾玖
11->壹拾壹
900->玖佰
909->玖佰零玖
111->壹佰壹拾壹
9000->玖仟
9009->玖仟零玖
1111->壹仟壹佰壹拾壹
90000->玖万
90009->玖万零玖
11111->壹万壹仟壹佰壹拾壹
900000->玖拾万
900009->玖拾万零玖
111111->壹拾壹万壹仟壹佰壹拾壹
9000000->玖佰万
9000009->玖佰万零玖
1111111->壹佰壹拾壹万壹仟壹佰壹拾壹
90000000->玖仟万
90000009->玖仟万零玖
11111111->壹仟壹佰壹拾壹万壹仟壹佰壹拾壹
900000000->玖亿
900000009->玖亿零玖
111111111->壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹
9000000000->玖拾亿
9000000009->玖拾亿零玖
1111111111->壹拾壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹
90000000000->玖佰亿
90000000009->玖佰亿零玖
11111111111->壹佰壹拾壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹
900000000000->玖仟亿
900000000009->玖仟亿零玖
111111111111->壹仟壹佰壹拾壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹
9000000000000->玖万亿
9000000000009->玖万亿零玖
1111111111111->壹万壹仟壹佰壹拾壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹
90000000000000->玖拾万亿
90000000000009->玖拾万亿零玖
11111111111111->壹拾壹万壹仟壹佰壹拾壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹
900000000000000->玖佰万亿
900000000000009->玖佰万亿零玖
111111111111111->壹佰壹拾壹万壹仟壹佰壹拾壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹
9000000000000000->玖仟万亿
9000000000000009->玖仟万亿零玖
1111111111111111->壹仟壹佰壹拾壹万壹仟壹佰壹拾壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹
90000000000000000->玖亿亿
90000000000000009->玖亿亿零玖
11111111111111111->壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹
900000000000000000->玖拾亿亿
900000000000000009->玖拾亿亿零玖
111111111111111111->壹拾壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹

Keep in mind that python doesn't optimize tail recursion. See http://stackoverflow.com/q/13591970/758446 — BlackVegetable, Oct 31 '13 at 17:16
Is that means there is no need to convert it to tail recursion? Oh, but I still want to know how to work it out. — tcpiper, Oct 31 '13 at 17:18
Well that's fine. I listed that as a comment to give perspective, not as an answer to give resolution. — BlackVegetable, Oct 31 '13 at 17:19
@Pythoner You can still essentially support a "tail recursive" structure if you transpose it to use Trampolines. — wheaties, Oct 31 '13 at 17:30
@wheaties thanks. It is a good thing. also gives me more motivation to find the tail recursion solution . — tcpiper, Oct 31 '13 at 17:36
@Pythoner Ping me in 2-3 days and I'll see if I can't answer this question. I just can't answer it right now. — wheaties, Oct 31 '13 at 23:03
@Pythoner let me see if I can't point you towards the right approach. — wheaties, Nov 03 '13 at 16:41

score 1 · Answer 1 · answered Nov 03 '13 at 17:12

Python doesn't support tail call elimination nor tail call optimizations. However, there are a number of ways in which you can mimic this approach (Trampolines being the most widely used in other languages.)

Tail call recursive functions should look like the following pseudo code:

def tail_call(*args, acc):
  if condition(*args):
    return acc
  else:
    # Operations happen here, producing new_args and new_acc
    return tail_call(*new_args, new_acc)

For your example I would not form a closure over anything as your are introducing side-effects and stateful manipulation. Instead, anything that needs to be modified should be modified in isolation of everything else. That makes it easier to reason about.

Copy whatever you're attempting to change (using string.copy for the final output) and pass it in as an argument to the next recursive call. That's where the acc variable comes into play. It's "accumulating" all your changes up to that point.

A classical trampoline can be had from this snippet. There, they are wrapping the function in an object which will eventually either result a result or return another function object which should be called. I prefer this approach as I find it easier to reason about.

This isn't the only way. Take a look at this code snippet. The "magic" occurs when it reaches a point which "solves" the condition and it throws an exception to escape the infinite loop.

Finally, you can read about Trampolines here, here and here.

Thank you! I will study them.I strongly feel I could answer my own question. — tcpiper, Nov 04 '13 at 02:58

score 0 · Answer 2 · answered Nov 06 '13 at 11:35

I keep studying this question off and on these days. and now, I work it out!

NOTE,not just tail-recursion, it's also pure Functional Programming!

The key is to think in a different way (tree-recursion version is processing numbers from left to right while this version is from right to left)

unitDic=dict(zip(range(8),u'拾佰仟万拾佰仟亿'))
numDic=dict(zip('0123456789',u'零壹贰叁肆伍陆柒捌玖'))
wapDic=[(u'零拾',u'零'),(u'零佰',u'零'),(u'零仟',u'零'),
        (u'零万',u'万'),(u'零亿',u'亿'),(u'亿万',u'亿'),
        (u'零零',u'零'),]

#pure FP
def ChnNumber(s):
    def wrapper(s,wd=wapDic):
        def rep(s,k,v):
            if k in s:
                return rep(s.replace(k,v),k,v)
            return s    
        if not wd:
            return s
        return wrapper(rep(s,*wd[0]),wd[1:])
    def recur(s,acc='',ind=0):        
        if s=='':
            return acc
        return recur(s[:-1],numDic[s[-1]]+unitDic[ind%8]+acc,ind+1)
    def end(s):
        if s[-1]!='0':
            return numDic[s[-1]]
        return ''
    def result(start,end):
        if end=='' and start[-1]==u'零':
            return start[:-1]
        return start+end
    return result(wrapper(recur(s[:-1])),end(s))

for i in range(18):    
    v1='9'+'0'*(i+1)
    v2='9'+'0'*i+'9'
    v3='1'*(i+2)
    print ('%s->%s\n%s->%s\n%s->%s'% (v1,ChnNumber(v1),v2,ChnNumber(v2),v3,ChnNumber(v3)))

if any one say that it won't work when facing a huge number(something like a billion-figure number), yeah, I admit that, but this version can solve it(while it will not be pure FP but pure FP won't need this version so..):

class TailCaller(object) :
    def __init__(self, f) :
        self.f = f
    def __call__(self, *args, **kwargs) :
        ret = self.f(*args, **kwargs)
        while type(ret) is TailCall :
            ret = ret.handle()
        return ret

class TailCall(object) :
    def __init__(self, call, *args, **kwargs) :
        self.call = call
        self.args = args
        self.kwargs = kwargs
    def handle(self) :
        if type(self.call) is TailCaller :
            return self.call.f(*self.args, **self.kwargs)
        else :
            return self.f(*self.args, **self.kwargs)

def ChnNumber(s):
    def wrapper(s,wd=wapDic):
        @TailCaller
        def rep(s,k,v):
            if k in s:
                return TailCall(rep,s.replace(k,v),k,v)
            return s    
        if not wd:
            return s
        return wrapper(rep(s,*wd[0]),wd[1:])
    @TailCaller
    def recur(s,acc='',ind=0):        
        if s=='':
            return acc
        return TailCall(recur,s[:-1],numDic[s[-1]]+unitDic[ind%8]+acc,ind+1)
    def end(s):
        if s[-1]!='0':
            return numDic[s[-1]]
        return ''
    def result(start,end):
        if end=='' and start[-1]==u'零':
            return start[:-1]
        return start+end
    return result(wrapper(recur(s[:-1])),end(s))

How to change this tree-recursion to a tail-recursion?

2 Answers2