python 递归的思想

什么是递归？

• 递归是自己调自己，但需要分解参数；
• 需要一个递归出口返回

def fact(n):
       if n == 0:
           return 1
        else:
           return n*fact(n-1)
print(fact(0))
=====================
1.递归必须包含一个基本的出口(base case),
  否则就会无限递归，最终导致栈溢出。
  比如这里就是n==0返回1

2.递归必须包含一个可以分解的问题(recursive case).
  要想求得fact(n),就需要用 n*fact(n-1)

3.递归必须要向着递归出口靠近(toward the base case).
  这里每次递归调用都会n-1,向着递归出口n==0靠近

实战---实现报数：
给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。
注意：整数顺序将表示为一个字符串。

代码实现：

# -*- coding:utf-8 -*-

class Solution(object):
    def countAndSay(self,n):
        if n == 1:
            return "1"
        return self.bs(self.countAndSay(n-1))

    def bs(self,string):
        lis = list(string)
        # 末尾补一个，方便后续计数
        lis.append('0')
        list1=[]
        re = 0
        i = 0
        while i<len(lis)-1:
            if lis[i] != lis[i+1]:
                list1.append(str(i+1-re))
                list1.append(lis[I])
                re = I+1
            i = I+1
        s = ''.join(list1)  #；列表转为字符串
        return s


if __name__ == "__main__":
    s = Solution()
    n= 4
    r = s.countAndSay(n)
    print r
======================
输出
1211