Recursive Fibonacci

So after bashing my head against the wall working on Fibonacci recursively and thinking "why on earth is this so slow," I realized the solution was reducing everything to a lot of ones and adding them all up. While addition and basic arithmetic for a CPU is exceptionally fast, this was slow due to the magnitude, and would cause way too much recursion for it to even be considered a correct solution. So I searched the web figuring someone far smarter than myself would have not only realized this, but come up with a real solution for it. Sure enough, I found one. The solution they used was in C, so I found it a bit ugly as it required two function calls (so you can call it with one argument). So I converted it to Haskell.

Before posting, the short explanation is this. Fibonacci numbers are found by adding up the previous two numbers. This is not to say you should call it inappropriately like this.

fib :: Integer-> Integer
fib 0 = 0
fib 1 = 1
fib x = fib (x - 1) + fib (x - 2)

However, this is often the solution I see in tutorials about recursion and very legitimate sources. I feel the reasoning for this is to use only one function call and as little code as possible to make an "elegant", or at least readable solution. The solution I found, while it is not the prettiest thing, it is far more efficient and very fast and after taking some time to really read it, makes far more sense true to the derivation of Fibonacci numbers. So here is the solution I found and converted to Haskell.

fib :: Integer-> Integer
fib 0 = 0
fib n =
    let
        fib2 1 _ n2 = n2
        fib2 x n1 n2 = fib2 (x - 1) n2 (n1 + n2)
    in
        fib2 n 0 1

Credit to the solution here. Glad to see people finding valid recursive solutions and letting people like myself know there's a better way.