【剑指offer】矩形覆盖

解题思路：
类似于上一道的找规律题；灵活应用递归和迭代

n的值为	一种有sum种方法
1	1
2	2
3	3
4	5
5	8

• 递归
• 迭代

讲一下递归和迭代的区别和各自的利弊

方法	定义	优点	缺点
递归	程序调用自身的编程技巧称为递归	1）大问题化为小问题,可以极大的减少代码量2）用有限的语句来定义对象的无限集合；3）代码更简洁清晰，可读性更好	1）递归调用函数,浪费空间；2）递归太深容易造成堆栈的溢出；
迭代	利用变量的原值推算出变量的一个新值，迭代就是A不停的调用B.	1）迭代效率高，运行时间只因循环次数增加而增加；2）没什么额外开销，空间上也没有什么增加，	1） 不容易理解；2） 代码不如递归简洁；3） 编写复杂问题时困难。

二者关系：
1） 递归中一定有迭代,但是迭代中不一定有递归,大部分可以相互转换。
2） 能用迭代的不用递归,递归调用函数,浪费空间,并且递归太深容易造成堆栈的溢出.（当然这一切都是相对的，不是绝对的）

---

Java

1、递归

public class Solution {
    public int RectCover(int target) {
        if(target<=2){
            return target;
        }
        return RectCover(target-1)+RectCover(target-2);
    }
}

2、迭代（相比较递归，空间上更为优化）

public class Solution {
    public int RectCover(int target) {
        if(target<=2){
            return target;
        }
        int a = 1;
        int b = 2;
        int sum = 0;
        for(int i = 2;i < target; i++){
            sum = a+b;
            a = b;
            b = sum;
        }
        return b;
    }
}

Python

1、递归

# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, number):
        if number<=2:
            return number
        return self.rectCover(number-1)+self.rectCover(number-2)
        # write code here

我们来分析一下，同样的思路，为啥python没有过？
而将递归改为迭代就过了？
第一个问题是因为语言自身的特性，这是语言自身的问题

第二个问题：就是我们之前提到的迭代和递归的优缺点，所以个人建议一般用迭代，减少递归的调用
2、迭代

# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, number):
        if number <= 2:
            return number;
        a = 1
        b = 2
        for i in range(2,number):
            a,b = b,a+b
        return b
        # write code here