What is recursion?

Recursion occurs when a function calls itself. This may seem counterintuitive at first, because you may think there can be only one copy of a function running at any particular time. However, each time you call a function, a separate instance of that function is created. Let's illustrate this with an example:

public class MyProgram {
    public static void main(String[] args) {
		example(1);
		System.out.println("goodbye");
	}
	
	static void example(int x) {
		if( x == 1 ) {
			System.out.println("first time!");
			example(2);              //the "recursive call"
			System.out.println("done with first time!");
		} else if( x == 2 ) {
			System.out.println("second time!");
		}
		//you don't need to write return; because void functions auto return at bottom
	}
}

When we trace the previous program, we see the following path: First, we start in main(). Then we run example(1). It outputs "first time!". Next, we run example(2), which outputs "second time!". Then, we return to example(1), because that is what called example(2). We print "done with first time!" here in example(1). Finally, we return to setup, where it prints "goodbye".

Remember the call stack from the previous section. You can picture it as a stack of papers. In computer science, we say that adding something to a stack is called a "push", while removing something from the top of a stack is called a "pop". Thus the previous program pushes main(), then pushes example(1), then pushes example(2), then pops example(2), then pops example(1), then finally pops setup(), which ends the program.

You might ask: what can we do with recursion that we can't already do with loops? Technically, nothing. However, some things are much harder to program without recursion than with recursion. Advanced programmers may choose to replace all recursion with loops and custom "stacks". In this chapter, we will first look at a few contrived examples where recursion is not recommended. Then, we will look at examples where recursion is preferred.

The mystery function example

Let's look at this mysterious recursive function. Don't run it yet! Can you guess what mystery(0) outputs? What about mystery(1)? mystery(5)?

public class MyProgram {
    public static void main(String[] args) {
		System.out.println(mystery(0));
		System.out.println(mystery(1));
		System.out.println(mystery(5));
	}
	
	static int mystery(int x) {
		if( x == 0 ) {
			return x;
		}
		return 1 + mystery(x-1);
	}
}

The answer to mystery(0) is simply 0, because in mystery if x is zero, it returns 0. When a function reaches a return statement, it exits immediately with that value

The answer to mystery(1) is 1. We can trace the call to see mystery(1) becomes 1 + mystery(0), which becomes 1 + 0, which is 1

mystery(5) is 5, although the path is much longer. mystery(5) becomes 1 + mystery(4) which becomes 1 + (1+mystery(3)) which becomes 1+(1+(1+mystery(2))) which becomes 1+(1+(1+(1+mystery(1)))) which becomes 1+(1+(1+(1+(1+mystery(0))))) which becomes 1+1+1+1+1+0, which is 5. You can tell from this breakdown that mystery(5) runs mystery six times!

Generally, mystery(x) is x for positive values of x. For negative values, this program crashes with a stackoverflow error, because it tries to do so much recursion that Java thinks we've gotten stuck in an infinite recursion (which we have). Additionally, mystery(x) runs the mystery function x+1 times. So even if we didn't crash, the program would take a very long time to run for large values of x

The mysterious fibonacci recursive function

Don't run it yet! Can you guess what f(2),f(3),f(4),f(5) and f(6) output?

public class MyProgram {
    public static void main(String[] args) {
		for(int i=2;i<7;i++) {
			println(f(i));
		}
	}
	
	static int f(int x) {
		if( x <= 2 ) { //We call this the "base case", it is required because
			return 1;       //a recursive function must sometimes not call itself
		}
		return f(x-1)+f(x-2);
	}
}

f(1) is 1 and so is f(2). Things get interesting when we do f(3), because it calls itself twice! Here's the stacktrace (path of execution):

//arrows denote "becomes":
//f(3) -> f(2)+f(1)
//   f(2) -> 1
//   f(1) -> 1
//f(3) -> 1 + 1 -> 2

And here is the stack trace for f(4):

//f(4) -> f(3)+f(2)
//   f(3) -> f(2)+f(1)
//      f(2) -> 1
//      f(1) -> 1
//   f(3) -> 1 + 1 -> 2
//   f(2) -> 1
//f(4) -> 2 + 1 -> 3

And here is f(5):

//f(5) -> f(4)+f(3)
//   f(4) -> f(3)+f(2)
//      f(3) -> f(2)+f(1)
//         f(2) -> 1
//         f(1) -> 1
//      f(3) -> 1 + 1 -> 2
//      f(2) -> 1
//   f(4) -> 2 + 1 -> 3
//   f(3) -> f(2)+f(1)
//      f(2) -> 1
//      f(1) -> 1
//   f(3) -> 1 + 1 -> 2
//f(5) -> 3 + 2 -> 5

As you can see, the execution path of f(5) is pretty long and complicated. Luckily, this problem is easy to do backwards on a piece of paper:

//f(1) -> 1
//f(2) -> 1
//f(3) -> f(2)+f(1) -> 2
//f(4) -> f(3)+f(2) -> 3
//f(5) -> f(4)+f(3) -> 5
//f(6) -> f(5)+f(4) -> 8
//f(7) -> f(6)+f(5) -> 13
//f(8) -> f(7)+f(6) -> 21
//f(9) -> f(8)+f(7) -> 34

Comparing Recursive Fibonacci with Loops

The previous f function is actually a pretty inefficient way of calculating the fibonacci series. You may have an intuitive notion that f runs itself a lot, however let's try to see exactly how much more. Here is a fibonacci function with just loops along side the recursive function:

public class MyProgram {
	static int numRuns = 0; //This variable exists across all functions
	
    public static void main(String[] args) {
		System.out.println(fib(10));
		System.out.println(f(10));
		System.out.println("fib ran once");
		System.out.println("f ran "+numRuns+" times"); //f ran 109 times
	}
	
	static int fib(int n) { //fib with loops
		int a=0,b=1;   //you can declare multiple variables per line
		for(int i=1;i<n;i++) {
			int tmp = a + b;
			a = b;
			b = tmp;
		}
		System.out.println("loop ran "+(n-1)+" times");
		return b;
	}

	static int f(int x) {
		numRuns++;
		if( x <= 2 ) { //We call this the "base case", it is required because
			return 1;       //a recursive function must sometimes not call itself
		}
		return f(x-1)+f(x-2);
	}
}

For an input of 10, the recursive function runs 109 times, while the non-recursive function runs once with 9 executions of the loop. In fact, the number of times f calls itself increases exponentially by a power of two, while the number of times fib loops increases linearlly with the input number. Thus, we would never want to use this exact fibonacci recursive function to find large fibonacci numbers.

Advanced students should note that the reason the recursive function is inefficient is that it is recomputing the same values over and over. The process of writing recursive algorithms without re-calculating values is sometimes called "dynamic programming". Dynamic programming is covered in CS03.

Using recursion to take a number to a power

Let us take an algorithm we have seen before,: integer exponents, and modify it to use recursion. Here's the function with loops:

public class MyProgram {
    public static void main(String[] args) {
		System.out.println(powerLoop(2, 10)); //1024
	}
	
	static int powerLoop(int base, int exp) {
		int out = 1;
		for(int i = 0 ; i < exp; i++) {
			out = out * base;
		}
		return out;
	}
}

To find the recursive algorithm, we first need to come up with a "base case", which is a situation where the solution is always a constant. Here we notice that if the exponent is zero, the result is always 1. Then, we need to express the higher powers in terms of lower powers. The trick for this problem is realizing that a to the power of b is the same as a * [a to the power of b-1]. With this inductive step in place, we can write the recursive exponent function:

public class MyProgram {
    public static void main(String[] args) {
		System.out.println(power(2, 10)); //1024
	}
	
	static int power(int base, int exp) {
		if(exp==0) {
			return 1;                    //the base case
		}
		return base*power(base,exp-1);   //the inductive step
	}
}

Using recursion to calculate factorial

One factorial, written as 1!, is 1. Two factorial, 2!, is 2*1 or 2. Three factorial, 3!, is 3*2*1 which is 6. Thus in general, n! is n*(n-1)*(n-2)*...*1 . For us to write a recursive function, we make the observation that n! is n*(n-1)!, which leads us to this:

public class MyProgram {
    public static void main(String[] args) {
		System.out.println(fac(10)); //3628800
	}
	
	static int fac(int x) {   //note: technically both 1! and 0! are 1
		if(x==0) return 1;    //curly brackets not required for 1 line if statement.
		return x*fac(x-1);
	}
}

Using recursion to reverse a string

Reversing a string of zero or one characters is trivial: you just return the string. Reversing a longer string is the same as attaching the first letter to the end and reversing the remaining characters. The tricky part is dealing with String syntax:

public class MyProgram {
    public static void main(String[] args) {
		System.out.println(rev("cat hat"));
	}
	
	static String rev(String x) {
		if(x.length()<=1) return x;  
		return rev(x.substring(1))+x.charAt(0); //x.substring(1) is all the characters of x excluding first character
	}
}

Using recursion to check if a string is a palindrome

A zero or one character string is always a palindrome. Otherwise, if the first character doesn't match the last then it's not a palindrome. If they match then we check if the subtring excluding the first/last is a palindrome:

public class MyProgram {
    public static void main(String[] args) {
		System.out.println(isPalindrome("cat hat"));
		System.out.println(isPalindrome("racecar"));
	}
	
	static boolean isPalindrome(String s) {
		if(s.length()<=1) return true;
		if(s.charAt(0)!=s.charAt(s.length()-1)) return false;
		return isPalindrome(s.substring(1,s.length()-1));
	}
}