在斐波那契数列中找到第n个项f（n）= f（n-1）+ f（n-2）可以通过记忆在O（n）时间内求解。
一种更有效的方法是使用分而治之在log n时间内求出矩阵[[1,1]，[1,0]]的n次幂。
对于f（n）= f（n-1）+ f（nx）+ f（n-x + 1）[x是某个常数]，是否可以遵循类似的方法。
只需存储先前的x个元素，就可以在O（n）时间内解决。
是否有更好的方法来解决此递归。
正如您已经怀疑的那样，这将非常相似。使用x * x矩阵的n次方
x * x
|1 0 0 0 .... 1 1| |1 | 1 | 1 | 1 | 1 ................... ................... | ... 1 0|
如果将此矩阵乘以向量，这很容易理解
f(n-1), f(n-2), ... , f(n-x+1), f(n-x)
导致
f(n), f(n-1), ... , f(n-x+1)
矩阵求幂可以在O（log（n））时间内完成（当x被认为是常数时）。
对于斐波那契递归，也有一个封闭公式解决方案，请参见http://en.wikipedia.org/wiki/Fibonacci_number，查找Binet或Moivre公式。
