Introduction

Recursion is more of a general technique than an algorithm. It is where a method calls itself. This is useful for many reasons. One is that it simulates a loop, but with more complex variables and increments. It also makes it very easy to code functions in terms of subproblems or divide and conquer.

Examples

Counting

This method counts down, using recursion:

void countDown(int num) {
	if (num == 1) {
		System.out.println(1);
		return;
	}
	System.out.print(num + " ");
	count(num - 1);
}

Calling countDown(5); will result in the following output: 5 4 3 2 1.

The method can be easily changed to make the method count up instead:

void countUp(int num) {
	if (num == 1) {
		System.out.print(1);
		return;
	}
	count(num - 1);
	System.out.print(num + " ");
}

Calling countUp(5); will result in the following output: 1 2 3 4 5.

Fibonacci

Another classical recursive method is the Fibonacci function. This function finds the $n^\text{th}$ Fibonacci number, starting from $1$:

The recursive function is defined with it’s base cases which are the terminating scenarios of a method which are required to end the recursion. In the two methods above, $num=1$ were the base cases. It is very easy to convert the recursive Fibonacci sequence to code.

int fib(int n) {
	if (n <= 2)
		return 1;
	return fib(n - 1) + fib(n - 2);
}

Stack Overflows

Another fundamental rule of recursion is that the method does not call itself with the same parameter, thus causing infinite loops. Similarly, there are other ways to achieve an infinite loop.

void inf(int n) {
	if (n == 0)
		return;
	if (n % 2 == 0)
		inf(n - 1);
	inf(n + 1);
}

Calling any values of n other than -1 or 0 will result in an infinite loop. Infinite loops in recursion should not occur when done properly. Note that recursion infinite loops don’t last forever. A stack overflow occurs very quickly. A StackOverflowError occurs when there are too many concurrent recursion calls thus running out of memory for the stack (where the stack variables are stored).

Recursive methods may use any instance variables in addition to the parameters. They may also create any new local variables within the method itself. You may pass anything into the method, including arrays, however, you should note what type of value passed (pass by reference/value).

Practice

DMOJ: Hailstone Numbers
DMOJ: Word Scrambler
TSOC ‘16 C1 P5 - Max and Cards
CCC ‘11 S3 - Alice Through the Looking Glass
MWC ‘15 #3 P3: Bad News
CCC ‘04 J5 - Fractals
CCC ‘13 J5/S3 - Chances of Winning