1

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

2 回答 2

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变量发挥作用的地方。到目前为止，它正在“累积”您的所有更改。

从这个片段可以得到一个经典的蹦床。在那里，他们将函数包装在一个对象中，该对象最终会产生结果或返回另一个应该调用的函数对象。我更喜欢这种方法，因为我发现它更容易推理。

这不是唯一的方法。看看这个代码片段。当它达到“解决”条件并抛出异常以逃避无限循环时，就会发生“魔术”。

最后，您可以在此处、此处和此处阅读有关蹦床的信息。

于 2013-11-03T17:12:48.940 回答
0

这些天我一直在研究这个问题。现在，我解决了！

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

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

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))
于 2013-11-06T11:35:05.003 回答