Blog|Meta Topics|Advanced Topics

Software Technology: Recursion

Assumed Knowledge:
Learning Outcomes:
  • Recognise difference between iterative and recursive code
  • Be able to trace recursive functions and methods
  • Be able to write recursive functions and methods

What is recursion?

There are two classical approaches to solving algorthmic problems:

  1. Iterative
  2. Recursive

Iterative solution

The distinctive property of iterative solutions is that they do not reduce a problem to a simpler form of itself.

EXAMPLE

Add all integers between low and high (inclusive on both sides, and assuming low <= high), I can go through each integer and add it to an accumulating variable, say total.

1
2
3
4
5
6
7
public static int sum(int low, int high) {
	int total = 0;
	for(int i=low; i<=high; i++) {
		total = total + i;
	}
	return total;	
}

Recursive solution

The distinctive property of recursive solutions is that they reduce a problem to a simpler form of itself.

EXAMPLE

For the same problem statement used for iterative solutions, we can say that the sum of all integers from low to high is:

1
2
3
4
5
if low <= high: 
	sub = sum of all integers from (low+1) to high
	return (low + sub)
else
	return 0

Focus on the part

1
sum of all integers from `low+1` to `high`

It is the same problem as the original problem, except there is one less number to handle, and thus is simpler.

Equivalence

It has been proven that there is a recursive solution for every iterative solution and vice versa. We will soon look at some of the aspects to consider while deciding on which approach to take.

Advantages

1. Intuitiveness

Some solutions have an intuitive recursive design. Some examples (we assume n >= 0 for all examples):

  1. x to the power of n:
    • xn = xn-1 * x if n > 0
    • x0 = 1
  2. number of digits in an integer:
    • nDigits(n) = nDigits(n/10) + 1 if n > 0
    • nDigits(0) = 0
  3. sum of the first n positive integers (1 + 2 + … + n):
    • sum(n) = sum(n-1) + n if n > 0
    • sum(0) = 0

2. Complex problems

While trivial problems have fairly obvious recursive and iterative solutions, it’s much easier to find a recursive solution to the more complex problems. For example, creating a random permutation of the word “super”.

random permutation of the word “super” = random character from “super” (say ‘u’) + random permutation of the word “sper”

random permutation of the word “sper” = random character from “sper” (say ‘r’) + random permutation of the word “spe”

random permutation of the word “spe” = random character from “spe” (say ‘s’) + random permutation of the word “pe”

random permutation of the word “pe” = random character from “pe” (say ‘e’) + random permutation of the word “p”

random permutation of the word “p” = random character from “p” (has to be ‘p’) + random permutation of the word “”

random permutation of the word “” = “” (end case)

Plugging the values back:

random permutation of the word “p” = ‘p’ + “” = “p”

random permutation of the word “pe” = ‘e’ + “p” = “ep”

random permutation of the word “spe” = ‘s’ + “ep” = “sep”

random permutation of the word “sper” = ‘r’ + “sep” = “rsep”

random permutation of the word “super” = ‘u’ + “rsep” = “ursep”

3. Recursive data structures

Advanced data structures (such as linked lists, trees and graphs) are recursive in nature and it is logical to operate recursively on them.

When should I not use recursion?

  1. Each method call requires:
    1. Variables associated with that call to be stored in the memory, thereby requiring more memory.
    2. Caller to transfer the control to the method called (callee), and then the callee to execeute and return control, possible with a value, back to the caller, thus adding to processing time. Hence, recursive solutions are generally have a little processing time overhead.

We will see concrete examples of this once we talk about recursive implementation.

What happens during a method call?

Before we jump into a method calling itself, it’s important to understand what happens when a method is called. Consider the following example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void main(String[] args) {
	int c = 1729;
	int d = foo(c);
	System.out.println(d);
}

public static int foo(int a) {
	int temp = bar(a);
	int result = temp * temp;
	return result;
}

public static int bar(int b) {
	int answer = b % 10;
	return answer;
}

STEP 1: main method is invoked by JVM

Method call is placed on the stack. Note that parameter is null because we typically do not pass any arguments to main, at least in this unit.<p>

STEP 2: main method calls foo with parameter c

Another entry is made for the call to foo and placed on the stack.<p>

STEP 3: foo calls bar with parameter a

A third entry is made for the call to bar and placed on the stack.<p>

STEP 4: bar returns value to foo

Entry for bar is taken off the stack. foo becomes the active method.<p>

STEP 5: foo returns value to main

Entry for foo is taken off the stack. main becomes the active method.<p>

STEP 6: Rest of main executes

Formal parameters vs. actual parameters

Each method expects zero or more values and gives the passed values some name. These are called formal parameters.

When the method is called, appropriate type of values (hopefully) are passed to it. These are called actual parameters.

Consider the following example:

1
2
3
4
public static int foo(int a) {
	int b = a*a;
	return b;
}

In the above example, a is the name of the formal parameter in method foo. Whenever, foo is called with a value of the right type (int), it (the passed value) is copied into variable a that stays in memory during the current execution of foo.

Here, a is the formal parameter.

Now let’s say the client code is:

1
2
3
4
5
public static void main(String[] args) {
	int p = 10;
	int q = foo(p);
	System.out.println(q);
}

The variable p is being passed as a parameter to method foo. Java checks it’s of the right type (int) and copies it into variable a during the execution of foo(p).

Here, p is the actual parameter.

Now consider a different client code:

1
2
3
4
5
public static void main(String[] args) {
	int a = 10;
	int result = foo(a);
	System.out.println(a);
}

Now we have a variable a in method main (represented by main: a) being passed to foo and copied into variable a, represented by foo(10): a. This is ok since the two variables, although with the same name, exist in different scopes. The following figure summarizes the transaction.

 

 

Method calling itself

When a method calls itself, another entry is added to the top of the method stack.

Consider the following code:

1
2
3
public static void foo() {
	foo();
}

This is the most basic recursive example, where the method foo calls itself, placing another instance on top of the stack.

Of course, since this process never terminates, the stack keeps growing infinitely. As you might imagine, there is a limit to the number of entries in the method stack and when this is reached, we get StackOverflowError.

Thus, our job is to ensure that methods don’t call themselves infinitely.

Consider the following code:

1
2
3
4
5
6
7
8
9
10
public static void main(String[] args) {
	int n = 4;
	foo(n);
}

public static void foo(int n) {
	System.out.println(n);
	int m = n-1;
	foo(m);
}

The output you will get before finally getting a StackOverflowError is:

1
2
3
4
5
6
7
8
9
10
4
3
2
1
0
-1
-2
-3
-4
and on and on and on ...

An illustration of memory transactions is given below

STEP 1: main calls foo(4)

STEP 2: foo(4) calls foo(3)

… and it repeats forever (ends with StackOverflowError)

End-case or terminal case is CRITICAL

It is critical that we have an end case of a terminal case.

1
2
3
4
5
6
7
public static void foo(int n) {
	if(n >= 1) {
		System.out.println(n);
		int m = n-1;
		foo(m);
	}
}

In the above modified method, we have enclosed the entire code in a conditional block. As soon as n drops below 1, it’s effectively an empty method body and it returns the control back to the caller.

1
2
3
4
5
6
7
8
9
10
main(null) calls foo(4)
	foo(4) displays 4 and calls foo(3) 
		foo(3) displays 3 and calls foo(2) 
			foo(2) displays 2 and calls foo(1) 
				foo(1) displays 1 and calls foo(0)
				foo(0) does nothing and returns control to foo(1)
			foo(1) returns control to foo(2)
		foo(2) returns control to foo(3)
	foo(3) returns control to foo(4)
foo(4) returns control to main(null)

The output you get is:

1
2
3
4
4
3
2
1

Following are two different ways of handling the terminal case:

1
2
3
4
5
6
7
8
public static int sum(int n) {
	if(n >= 1) {
		return n + sum(n-1);
	}
	else {
		return 0;
	}
}
1
2
3
4
5
6
public static int sum(int n) {
	if(n >= 1) {
		return n + sum(n-1);
	}
	return 0;
}
1
2
3
4
5
6
7
8
public static int sum(int n) {
	if(n < 1) {
		return 0;
	}
	else {
		return n + sum(n-1);
	}
}
1
2
3
4
5
6
public static int sum(int n) {
	if(n < 1) {
		return 0;
	}
	return n + sum(n-1);
}

First look at a recursive solution

PROBLEM STATEMENT

Define a method that when passed an integer, returns the sum of all integers from 1 to that integer.

Examples:

Input = 4 -> return 1 + 2 + 3 + 4 (10)

Input = 6 -> return 1 + 2 + 3 + 4 + 5 + 6 (21)

Let’s call the method sum and the the formal parameter n

sum(n) = 1 + 2 + … + (n-1) + n

can be written as:

sum(n) = [1 + 2 + … + (n-1)] + n

But

[1 + 2 + … + (n-1)] is sum(3)

(by the problem statement)

Hence,

sum(n) = sum(n-1) + n

First attempt

1
2
3
public static int sum(int n) {
	return sum(n-1) + n;
}

But this version will result in the method calling itself indefinitely, until JVM causes StackOverflowError.

We need to address the end case:

sum(0) = 0

Seond attempt

1
2
3
4
5
6
7
public static int sum(int n) {
	if(n == 0) {
		return 0;
	}
	//control reaches here only if n is not 0
	return sum(n-1) + n;
}

What happens if the client, maliciously, calls the method with parameter -3?

sum(-3) -> sum(-4) -> sum(-5)

Since the parameter is never equal to 0, the method, when initially called with a negative value, calls itself indefinitely.

Eventually JVM causes StackOverflowError.

Third (and correct) version

1
2
3
4
5
6
7
public static int sum(int n) {
	if(n <= 0) { //return 0 for anything less than 1
		return 0;
	}
	//control reaches here only if n is more than 0
	return sum(n-1) + n;
}

Trace

1
sum(4)	= sum(3) + 4
1
	sum(3)	= sum(2) + 3
1
		sum(2)	= sum(1) + 2
1
			sum(1) = sum(0) + 1
1
				sum(0)	returns 0 (terminal case)
1
			sum(1) returns 0 + 1 (1)
1
		sum(2) returns 1 + 2 (3)
1
	sum(3) returns 3 + 3 (6)
1
sum(4) returns 6 + 4 (10)

Summarized trace

1
2
3
4
5
6
7
8
9
10
11
main(null) calls sum(4)
	sum(4) calls sum(3)
		sum(3) calls sum(2)
			sum(2) calls sum(1)
				sum(1) calls sum(0)
				sum(0) returns 0 to sum(1)
				sum(1) adds 1 to the received value (0) and returns 1 to sum(2)
			sum(2) adds 2 to the received value (1) and returns 3 to sum(3)
		sum(3) adds 3 to the received value (3) and returns 6 to sum(4)
	sum(4) adds 4 to the received value (6) and returns 10 to main()
main(null) uses the received value (10) as needed