如何将这种树形递归改为尾递归？

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不支持尾部调用消除，也不支持尾部调用优化。但是，有许多方法可以模仿这种方法(在其他语言中使用最广泛的是Trampolines)。

尾部调用递归函数应该看起来像以下伪代码：

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