Recursion is a programming technique that deconstructs a large process into a series of small, identical steps. Thus, a single method is created that continually calls itself to solve the next iteration by altering the parameters. This continues until some termination criterion is reached.
While recursion is a useful tool, it requires additional memory to store the recursive stack. That is, each time a method invokes itself, it has to “pause” its current execution while the next call is performed. Eventually, these calls will be resolved until the original method invocation is reached, terminating the process. The information required for these pauses is stored in a call stack, which is typically referred to as the recursive stack during recursion. The depth of recursion determines the amount of memory required for this process – the deeper it goes (i.e., the more recursive calls), the larger the allocation.
A common recursive Java Exception is java.lang.StackOverflowError, which simply means the number of calls exceeds the amount of memory reserved for the stack. One can increase the stack size using -Xss#{k|K|g|G|m|M} – e.g., to set the stack size to 1MB, -Xss1M (defaults).
Recursive example
One of the easiest recursive examples is the calculation of \(x!=\prod_{i=1}^{x}i\). Each iteration \(i\) is simply the product of the current value \(x_{i}\) and previous solution \(x!_{i-1}\), producing \(x!_{i}=x_{i}x!_{i-1}\) for each recursive call. The code below illustrates this process.
The main point of confusion lies in how the method xFactorial(x) operates. Essentially, assuming \(x > 1\), line 16 is repeatedly called until \(x == 1\). Once that occurs, the previous values are returned up the stack until the method terminates by returning \(x!_{i}=x_{i}x!_{i-1}\).
For example, let \(x = 5\):
Calls:
\(5*xFactorial(5-1)\)
\(~~~~4*xFactorial(4-1)\)
\(~~~~~~~~3*xFactorial(3-1)\)
\(~~~~~~~~~~~~2*xFactorial(2-1)\)
Returns:
\(~~~~~~~~~~~~~~~~return~1\)
\(~~~~~~~~~~~~return~2*1\)
\(~~~~~~~~return~3*2\)
\(~~~~return~4*6\)
\(return~5*24\)
Thus, \(5!=120\).
/**
* Computes x! recursively.
* @author Ray Hylock
*/
public class Recursion {
/** Do not instantiate. */
private Recursion(){}
/**
* Compute x! recursively.
* @param x x
* @return x!
*/
public static long xFactorial(long x){
if(x == 0 || x == 1) return 1;
return x*xFactorial(x-1);
}
public static void main(String args[]){
long x = 5;
System.out.println(x + "! = " + xFactorial(x));
}
}Output for the example:
5! = 120