Avoiding Recursion

Another common optimization technique that may speed up program execution and that definitely saves memory is to transform recursions into iterations. You can usually do so if there is only one simple recursion call. For example, the factorial of a number n is defined as n multiplied by the factorial of (n-1). The corresponding recursive function is

public static void fact (int n) {
    return n == 1 ? 1 : n * fact (n – 1);
}

The problem with recursion is that it consumes stack space: The return address and local variables are stored on the program stack when a method is called. Also, the program state changes that correspond to a method call might take more time than a simple loop.

Thus, for the function defined previously, the following iterative function may be more efficient:

public static void fact (int n) {
    int result = 1;
    while (n > 1) result *= n--;
    return result;
}

Obviously, the tradeoff is that the iterative constructs are often less readable than the recursive versions.