数据结构-递归

递归定义：递归(Recursion)是指在函数的定义中使用函数自身的方法

递归使用的3个条件：

1.问题可以拆解成多个子问题

2.拆解后的问题求解思路一样，除了规模不同

2.有终止条件

递归构建步骤：

第一步：定义函数，先不考虑函数的功能

    def fun(n):

         pass

第二步：找到终止条件

   def fun(n):

        if(n==1):

             return 1

第三步：寻找问题拆解后和子问题之间的关系

 def fun(n):

        if(n==1):

             return 1

       return fun(n-1)+fun(n-2)