如何将这个treerecursion更改为tailrecursion？

Question

我正在编写一个函数ChrNumber，将阿拉伯数字字符串转换为中文金融数字字符串。我计算出一个树递归形式。但是当我试图得到一个尾部递归形式时，我真的很难处理bit等于6、7、8或10以及更大的情况。你知道吗

你可以在我问题的结尾看到它是如何工作的。你知道吗

下面是树递归解决方案。它的工作原理是：

# -*- 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))

我的尝试版本只在recur函数中，我使用了一个闭包res，并将bit移到recur内，因此参数更少

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

测试代码为：

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))

应输出：

>>> 
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->壹拾壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹

Answer 1

Python不支持尾部调用消除和尾部调用优化。但是，有很多方法可以模仿这种方法（蹦床在其他语言中使用最广泛）

尾部调用递归函数应类似于以下伪代码：

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)

对于你的例子，我不会形成一个封闭的任何东西，因为你是介绍副作用和有状态的操纵。相反，任何需要修改的内容都应该与其他内容隔离地进行修改。这样就更容易推理了。你知道吗

复制要更改的内容（使用string.copy作为最终输出），并将其作为参数传递给下一个递归调用。这就是acc变量发挥作用的地方。它“累积”了你所有的变化。你知道吗

古典蹦床可以从this snippet开始。在那里，他们将函数包装在一个对象中，这个对象最终要么产生一个结果，要么返回另一个应该被调用的函数对象。我更喜欢这种方法，因为我发现它更容易推理。你知道吗

这不是唯一的办法。看看this code snippet。当它到达一个“解决”条件的点，并且抛出一个异常来逃避无限循环时，“魔法”就发生了。你知道吗

最后，你可以阅读蹦床here、here和here。你知道吗

Answer 2

这些天我断断续续地研究这个问题。我现在就努力！

注意，不仅仅是尾部递归，它也是纯函数编程！

关键是以不同的方式思考（树递归版本是从左到右处理数字，而这个版本是从右到左）

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)))

如果有人说它在面对一个巨大的数字（比如十亿位数）时不起作用，是的，我承认，但是这个版本可以解决它（虽然它不是纯FP，但是纯FP不需要这个版本）

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))