Memoization is an optimization technique that caches computationally expensive function calls. I first learned of it in Stanford's Algorithms class on Coursera.1 It is more common in functional programming than object oriented programming because the function being cached can not have any side-effects, and that is, of course, often the case in functional programming. It is also commonly used by lazy data structures. The downside of memoization is that more memory will be used, but for some functions, as you will see below, it is well worth it.
A function that returns the nth Fibonacci number is the quintessential recursive function. I still remember that was the example used when I first learned of recursion. It is actually often implemented inefficiently, though, the standard recursive implementation being O(fib(n)) = 2n.
Python
Python makes memoization easy because you can decorate any function with a memoization function.
Scala
Scala does not make it that simple. Hopefully it will be built into the language in the future. This naive implementation only caches the original function call. The recursive calls do not know to use the memoized wrapper.
This blog correctly points out this problem with memoizing a recursive function and has a great technical explanation of the solution. In summary, you have to use something called a Y combinator to correctly implement the memoized wrapper function in Scala. It is basically a high-order function that returns a recursive version of a non-recursive function. I will defer to these other resources for a proper definition.
Notes
In Scala, for example, I could get up to n=45 in about 20 seconds with the standard un-memoized Fibonacci implementation. With the correctly memoized version I can run n=1000 in under 1 second because the memoized recursive implementation is O(fib(n)) = n.
The recursive Fibonacci implementation is not tail-recursive (which I covered in a previous blog), so you pretty quickly will hit a stack overflow error. In my Python implementation I even had to explicitly set the recursion limit higher than the default.
Also note the use of currying (which I also covered in a previous blog) in the nonRecursiveFibonacci Scala function.
1 I would highly recommend this class. It is better than the algorithms class I paid for to get my CS degree.