Is that really tail recursion though ? Seems like you are making two recursive calls to fib(). I thought tail recursion requires a single final call to recursive function.

Your memorization helps, but seems you will still run out of stack space if you call it with a big number without a warm up.