This article will have quite a few equations but they are not as hard to follow as they look so bear with me.
Every programmer has written a program that finds the nth Fibonacci number. Some of you did it with recursion, others went a step ahead and used dynamic programming. Still, even with dynamic programming your algorithm was . We can go even further and write an algorithm for finding the nth number of any sequence of the type:
where is a positive integer, are some constants and is the (n  i)th member of the sequence. A sequence defined as above is called a linear recurrence homogenous relation (LRHR) of order k.
Clearly, the Fibonacci sequence is a LRHR of order k = 2 since it is defined as:
Let me now show you how to compute the nth Fibonacci number not only in time complexity of , but also in constant space complexity (in contrast to dynamic programming which requires linear)
To do so we must find a closed form of our relation. We'll explore how to do that by first giving the general solution to such a problem and then applying it to the Fibonacci sequence as an example.
Algorithm for solving linear recurrence homogenous relations

In the equation replace all the with and you get:
Call the polynomial a characteristic polynomial.
Applied to our example:
Replacing the as described above gives us .
Therefore, the characteristic polynomial of the Fibonacci sequence is .

Find the roots of the characteristic polynomial.
Applied to our example:
Roots of the Fibonacci's polynomial are . (As a side note, the number is known as the Golden Ratio)

Let the roots of the characteristic polynomial be . For now let's assume that there are no repeated roots. Then the closed form of our sequence is
where are some unknown (for now) constants.
We will consider the repeated roots case later.
Applied to our example:
For the Fibonacci sequence, applying step 3 gives us:

Given that you know the first members of the sequence, you can now calculate the unknown constants by substituting the values of the first members in the equation of step 3.
Applied to our example:
The first two members of the Fibonacci sequence are .
Substitute for and we get:
Substitute for and we arrive at:
But since we just found out that :
Therefore:

Go back to the equation in step 3 and replace all the with the values that you just calculated to receive the final closed form.
Applied to our example:
Substitute in and:
Finally, the closed form of the Fibonacci sequence is:
Obviously the above formula can be calculated in so that completes our algorithm.
Here's an example implementation in C#. I tested it by computing the first 92 Fibonacci numbers a million times (the 92^{nd} number is the last one that can be stored in a Int64). Results prove that direct computation with the formula is much faster(every number was calculated a million times in ~0.17s), while dynamic programming is slower for all numbers after the 18^{th}. Average running time (over 10 tests):
Direct formula 
Dynamic programming 
15.8 s 
33.575 s 
Here's the same code implemented in JavaScript for you to play with.
There are a few things to note though:
 The roots in the Fibonacci polynomial are not integers. Therefore, we cannot hope to effectively calculate every single number in the sequence due to floating – point arithmetic errors. Test the example implementations above and see for yourself that the last number to be calculated correctly is the 71^{st} for the C# code and the 75^{th} for the JS one. If the roots were integers it would've been a whole another story.
 In the JS example, even the dynamic programming approach fails after 78^{th }number due to the way JavaScript integers work. To see the error, compare the results from our example with this calculator.
Repeated Roots
Now as promised let's take a look at what happens when one of the roots of the characteristic polynomial is repeated (step 3). For simplicity's sake, let's assume that only the first root is repeated and let denote the number of times it is repeated. The last statement is equivalent to saying that the roots of our polynomial are . In this case, our closed form solution will look like this:
(Of course if more than one root repeats, do the same for it)
And since that last equation looks a little horrifying, let's give an example. The characteristic roots of the sequence are .
Applying what we said above we get the following closed form:
Say that the first 2 members of the sequence are 0 and 1 as in the Fibonacci numbers. Substitute for and you get:
Substitute :
Therefore the closed form solution of the relation is precisely:
Summary:
For every linear recurrence homogenous relation there exists a closed form solution. Hence, since you can model any recursive function like a sequence, you can find a closed form for every recursive function knowing only its first few values.
This algorithm may not be the remedy for everything, but it sure kicks your recursive function into turbo mode. Best results are achieved when the roots of the characteristic polynomial are integers and the sequence is slowly increasing (unlike the Fibonacci which quickly overflows 64bits).
It may not always be the case you need the performance boost from using LRHR over DP but it is always a good thing to know that such an algorithm exists if a problem of this kind arises.
Things to note:
 The order must be a constant. (i.e. the factorial function cannot be solved by the above algorithm since it depends on all previous values which is a variable amount)