algorithm - 如何解决条件线性递归？

Question

如何解决条件线性递归问题？？
例如，

f[1]=m;  
f[i]=f[i-1]*m; if i is even
f[i]=(f[i-1]-2)*2 +2 if i is odd  

计算f[n]
如果只是一个简单的线性递归，f[n] 可以在 O(log N) 时间内计算出来，但是如何处理两个不同的递归？？

Answer 1

f[i] = (f[i - 2] * m - 2) * 2 + 2 if i is odd
f[i] = ((f[i - 2] -2) * 2 + 2) * m if i is even

现在分别解决这两个递归问题。我将您的公式相互替换，目的是让偶数和奇数指数仅取决于相同的奇偶性。