如何將此樹遞歸更改爲尾遞歸？

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'') 
#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和移動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 

的測試代碼裏面bit：

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('',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))