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

Author: Gaurav Gupta

What is recursion?

There are two common approaches to solving algorithmic problems - iterative and recursive.

1. Iterative solution

The distinctive property of recursive solutions is that they 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;
}

2. Recursive solution

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

One example (shared by one of the students on MACS Discord) is if you are standing at the back of a very long queue, and you want to know how many people are in that queue.

drawing

  • You ask the person in front of you, “How many people are in front of you?”,
  • The person in front of you asks the person in front of them, “How many people are in front of you?”,
  • That person asks the person in front of them, “How many people are in front of you?”,
  • That person asks the person in front of them, “How many people are in front of you?”,
  • That person asks the person in front of them, “How many people are in front of you?”,
  • and this keeps going down the queue,
  • until …
  • it reaches the first person in the queue (base case), and that person will say “There is ONE person in the queue - me!”.
  • the second person in the queue gets that answer (ONE), adds one to it (for themselves), and says “TWO” to the person behind them.
  • the third person in the queue gets that answer (TWO), adds one to it (for themselves), and says “THREE” to the person behind them.
  • So each person adds one to the answer they get and that’s the answer they give the person behind them.
  • until you get back to the person who originally asked the question, and then they have the answer.

EXAMPLE 2

Now, 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:
    return 0
else:
    sub = sum of all integers from (low+1) to high
    return (low + sub)

Focus on the part,

1

sum of all integers from (low+1) to high

This is analogous to the same question we ask the person in front of us in the queue example.

And our contribution to the answer is adding low to the answer we get.

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?

Recursion has it’s own set of disadvantages. 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 execute and return control, possible with a value, back to the caller, thus adding to processing time. Hence, recursive solutions have overhead in terms of time.

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

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

Second 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
2
3
4
5
6
7
8
9
10

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

Variations

Some variations of sum function are provided to help you understand recursion better:

  1. sumOdd(int): sum of positive ODD numbers up to, and including, the parameter

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

     public static int sumOdd(int n) {
     if(n <= 0) {
         return 0;
     }

     if(n%2 == 0) { //when initially called with an even parameter
         return sumOdd(n-1);
     }

     //guaranteed: n >= 1 AND n%2 != 0 => n is a positive, odd number

     return n + sumOdd(n-2);
     //add the current odd number to
     //the sum of all odd numbers up to, and including n-2
 }

  2. sumSquares(int): sum of squares pf positive integers up to, and including, the parameter

    1
2
3
4
5
6
7
8
9

     public static int sumSquares(int n) {
     if(n <= 0) {
         return 0;
     }

     return n*n + sumSquares(n-1);
     //add the square of the current number to
     //the sum of all square integers up to, and including n-1
 }

  3. sumSquareOdds(int): sum of squares of positive ODD numbers up to, and including, the parameter

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

     public static int sumSquareOdds(int n) {
     if(n <= 0) {
         return 0;
     }

     if(n%2 == 0) {
         return sumSquareOdds(n-1);
     }

     //guaranteed: n >= 1 AND n%2 != 0 => n is a positive, odd number

     return n*n + sumSquares(n-2);
     //add the square of the current number to
     //the sum of all square integers up to, and including n-2
 }

  4. sumDigits(int): sum of the digits of a number

    1
2
3
4
5
6
7
8
9
10
11
12
13
14

     public static int sumDigits(int n) {
     if(n == 0) {
         return 0;
     }

     if(n < 0) { //just in case n is negative
         return sumDigits(-n);
     }

     int lastDigit = n%10;
     int remainingNumber = n/10;

     return lastDigit + sumDigits(remainingNumber);
 }

  5. getReversed(String): get reverse of a String

    1
2
3
4
5
6
7
8
9
10

     public static String getReversed(String str) {
     if(str == null || str.length() < 1) {
         return str;
     }

     char first = str.charAt(0);
     String remaining = str.substring(1);

     return getReversed(remaining) + first;
 }

  6. isPalindrome(String): return true if String is same when reversed, false otherwise

    1
2
3
4
5
6
7
8
9
10

     public static boolean isPalindrome(String str) {
     if(str == null) {
         return false;
     }
     if(str.length() < 1) {
         return true;
     }

     return str.equals(getReversed(str));
 }

Note that this method uses getReversed as a helper, which, in turn, is recursive.

Relevant MQ Videos