什么是递归？
- 递归是自己调自己，但需要分解参数；
- 需要一个递归出口返回
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
