Where there is recurrence , there is Matrix Expo.
We use matrix expo to calculate very large number, terms of the recurrence where even DP can’t help us to pre-calculate the result.
You are all requested to read this blog Matrix Expo for understanding the matrix exponentiation.
Here is a sample code for generating Fibonacci numbers.
Note: For different types of recurrence , the base matrix will change accordingly. We have to generate this base matrix carefully , else every other things are pretty much same.