An introduction to lockless algorithms

With that implementation, there's a good chance you'll experience integer wraparound (and thus wrong results) before you blow the stack. fib(92) = 7540113804746346429, fib(93) = 12200160415121876738 which doesn't fit in a 64-bit signed integer.

The problem with the recursive solution is the exponential runtime; the stack usage is linear.