递归：将问题分解成子问题求解，从较小的问题逐渐逼近原始问题，很多时候只需要在f（n-1）中加入或移除某些东西或稍作修改就可以求得f（n）
递归 是 考虑所有的情况，一般使用搜索（DFS /BFS）来实现。
一般可以使用记忆化搜索进行优化的递归算法，我们可以使用DP来进行优化。
斐波那契系列问题 经典斐波那契问题代码就不写了，这个基本都会，需要注意的是：
递归方法的时间复杂度是：$O(2^N)$
顺序计算的时间复杂度是：$O(N)$
二阶递推数列的时间复杂度是：$O(logN)$
大牛小牛问题假设农场中成熟的母牛每年只会生1头小母牛，并且永远不会死。
第一年农场有1只成熟的母牛，从第二年开始，母牛开始生小母牛。
每只小母牛3年之后成熟又可以生小母牛。
给定整数N，求出N年后牛的数量。
【举例】N=6，第1年1头成熟母牛记为a；
第2年a生了新的小母牛，记为b，总牛数为2；
题目最优解第3年a生了新的小母牛，记为c，总牛数为3；
第4年a生了新的小母牛，记为d，总牛数为4。
第5年b成熟了，a和b分别生了新的小母牛，总牛数为6；
第6年c也成熟了，a、b和c分别生了新的小母牛，总牛数为9，返回9。
【要求】对以上所有的问题，请实现时间复杂度O(logN)的解法。
有 $F(N)=F(N-1)+F(N-3)$
用一个矩阵乘法，且状态矩阵为$3*3$
public int c3(int n){ if(n<1){ return 0; } if(n==1||n==2||n=3){ return n; } int base[][]={{1,1,0},{0,0,1},{1,0,0}}; //构造矩阵 int [][] res = matrixPower(base,n-3); //矩阵n-3次方 return 3*res[0][0]+2*res[1][0]+res[2][0]; }