One thing comes in mind is memoization. Simple well studied problem for this is Fibonacci numbers, simple recursion is as follow:
fib(int n)
{
if (n < 3)
return 1;
return fib(n-1) + fib(n-2);
}
But with memoization, we can use an auxiliary array to get rid of extra calls:
f[1]=f[2] = 1;
fib(int n)
{
if (n < 3)
return 1;
if (f[n] == 0)
f[n] = fib(n-1) + fib(n-2);
return f[n];
}
This simple change, reduces the time from $\Theta(\phi^n)$ to $\Theta(n)$.
The memoization technique sometimes uses more memory, but very faster in time, and one of a tradeoffs that software developer should be care about it is this.
Explanation of the memoization of Fibonacci numbers:
First we create an array $f$, to save the values that already computed. This is the main part of all memoization algorithms. Instead of many repeated recursive calls we can save the results, already obtained by previous steps of algorithm. As shown in the algorithm we set the $f[1],f[2]$ to $1$.
In the first if we actually check whether we are in the start or not. But we can remove this if statement. But for make it simpler to read I left it.
In the second if, we check if the value of fib(n) is already computed or not. This prevents us from multiple call for the same number, for example suppose we want to compute f(6), then in normal recursion we have the first recursion tree as shown in the following figure and in the memoization version we have the second tree. The reason is, in memoization we just compute the green vertices one time and then we save them into the memory (array $f$) and if needed we fetch them later.
In the following figure, green nodes are parts which are necessary to be computed (in this way), yellow nodes are precomputed ones, and red nodes are the nodes that are repeatedly computed in the first recursion.
As is clear from the image, in the normal case we have just precomputed f(1) and f(2), but in the memoization case, all functions for less than $n-1$ are precomputed, and this causes exponentially smaller recursion tree. (In memoization number of red nodes is zero, which is exponential in the normal recursion).
