12/10到12/11的做题总结

一，递归的一些方法；

从斐波拉契数列和一个题目得到

1.首先我们要找到递归关系，可用归纳法，最后得到f(n)=f(n-1)+f(n-3)

2.从斐波拉契数列我之前知道4个方法

1,return f(n)=f(n-1)+f(n-2)但这个不好易超时，假如要求f(10),我们要算f(1),f(2)等等；

2.我们思考那我主要记住算过的值不就好了，有以下代码缺点为太麻烦，有些东西太麻烦了，他的想法为将所有值用一个不可能的-1替代，当有值！=-1则代表这个值是被记住的；然后用这个值计算就行了

3.最好的方法，一个思路，一个滑动的思路，诞生有俩种方法，滚动数组和尾递归；

首先滚动数组，思路为，设a,b以及结果a+b,有此思考，下一项则是，原来的a变为b,b为a+b,新结果则为新a+b,代码为尾递归同样滑动的思路，用不到循环了，因为用函数实现了，其思路为一个记录开始值，一个记录运算和要结束的条件你看其核心为绿色代码，上面为判断返回因为n一直递减，执行公式（此题是f(n)=f(n-1)+f(n-3)）

要用到三个变量所有比斐波拉契复杂一些，下面函数为主函数接口，为n的前置条件和他的开始值

return cowtail(n - 1, b, c, a + c); 这个重要，而且我们也可以写斐波拉契的

return cowtail(n-1;b;a+b)//新a为原b,新b为原a+b