This is also the perfect playground for Memoize, because it will handle intermediate calls caching allowing you to concentrate into the main stuff. Fun is that the example for the Memoize module actually deals with the Fibonacci sequence!