title: How to change this tree-recursion to a tail-recursion?
body: <p>I am writing a function <code>ChrNumber</code> 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 <code>bit</code> equals 6,7 or 8 or 10 and bigger ones.</p>
  
  <p>You can see how it works at the end of my question.</p>
  
  <p>Here's the tree-recursion solution. It works:</p>
  
  <pre><code># -*- 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&lt;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&lt;9:
              return u'%s%s%s' % (recur(s[:-4],bit-4),u"万",recur(s[-4:],4))
          if bit&gt;9:
              return u'%s%s%s' % (recur(s[:-8],bit-8),u"亿",recur(s[-8:],8))
      return recur(s,len(s))
  </code></pre>
  
  <p>My attempt version is only in <code>recur</code> function, I use a closure <code>res</code> and move the <code>bit</code> inside the <code>recur</code> so there is less arguments.:</p>
  
  <pre><code>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&lt;6 or bit==9:
          res.append(u'%s%s' %(numDic[s[0]],unitDic[bit]))
          return recur(s[1:])
      if bit&lt;9:
          #...can't work it out
      if bit&gt;9:
          #...can't work it out
  </code></pre>
  
  <p>the test code is:</p>
  
  <pre><code>for i in range(17):
      v1='9'+'0'*(i+1)
      v2='9'+'0'*i+'9'
      v3='1'*(i+2)
      print '%s-&gt;%s\n%s-&gt;%s\n%s-&gt;%s'% (v1,ChnNumber(v1),v2,ChnNumber(v2),v3,ChnNumber(v3))
  </code></pre>
  
  <p>which should output:</p>
  
  <pre><code>&gt;&gt;&gt; 
  90-&gt;玖拾
  99-&gt;玖拾玖
  11-&gt;壹拾壹
  900-&gt;玖佰
  909-&gt;玖佰零玖
  111-&gt;壹佰壹拾壹
  9000-&gt;玖仟
  9009-&gt;玖仟零玖
  1111-&gt;壹仟壹佰壹拾壹
  90000-&gt;玖万
  90009-&gt;玖万零玖
  11111-&gt;壹万壹仟壹佰壹拾壹
  900000-&gt;玖拾万
  900009-&gt;玖拾万零玖
  111111-&gt;壹拾壹万壹仟壹佰壹拾壹
  9000000-&gt;玖佰万
  9000009-&gt;玖佰万零玖
  1111111-&gt;壹佰壹拾壹万壹仟壹佰壹拾壹
  90000000-&gt;玖仟万
  90000009-&gt;玖仟万零玖
  11111111-&gt;壹仟壹佰壹拾壹万壹仟壹佰壹拾壹
  900000000-&gt;玖亿
  900000009-&gt;玖亿零玖
  111111111-&gt;壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹
  9000000000-&gt;玖拾亿
  9000000009-&gt;玖拾亿零玖
  1111111111-&gt;壹拾壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹
  90000000000-&gt;玖佰亿
  90000000009-&gt;玖佰亿零玖
  11111111111-&gt;壹佰壹拾壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹
  900000000000-&gt;玖仟亿
  900000000009-&gt;玖仟亿零玖
  111111111111-&gt;壹仟壹佰壹拾壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹
  9000000000000-&gt;玖万亿
  9000000000009-&gt;玖万亿零玖
  1111111111111-&gt;壹万壹仟壹佰壹拾壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹
  90000000000000-&gt;玖拾万亿
  90000000000009-&gt;玖拾万亿零玖
  11111111111111-&gt;壹拾壹万壹仟壹佰壹拾壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹
  900000000000000-&gt;玖佰万亿
  900000000000009-&gt;玖佰万亿零玖
  111111111111111-&gt;壹佰壹拾壹万壹仟壹佰壹拾壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹
  9000000000000000-&gt;玖仟万亿
  9000000000000009-&gt;玖仟万亿零玖
  1111111111111111-&gt;壹仟壹佰壹拾壹万壹仟壹佰壹拾壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹
  90000000000000000-&gt;玖亿亿
  90000000000000009-&gt;玖亿亿零玖
  11111111111111111-&gt;壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹
  900000000000000000-&gt;玖拾亿亿
  900000000000000009-&gt;玖拾亿亿零玖
  111111111111111111-&gt;壹拾壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹
  </code></pre>