Recursion

Recursion means a method calling itself, either directly or indirectly.

Textbook Basic Example

Recursive.java  
RecursionDemo.java  
Although there is some value in having the function be in a separate class, it does little to elucidate what is happening. Better to combine them:

MyRecursionDemo
public class MyRecursionDemo {
  public static void main(String[] args) {
    int n = 4;
    message(n);
    // done-main
    System.out.printf("--- done:main(%d)\n", n); 
  }
 
  public static void message(int n) {
    System.out.printf("message(%d)\n", n);
    if (n > 0) {
      message(n - 1);
      // done-message
      System.out.printf("--- done:message(%d)\n", n-1); 
    }
  }
}
select
The output is:
message(4)
message(3)
message(2)
message(1)
message(0)
--- done:message(0)
--- done:message(1)
--- done:message(2)
--- done:message(3)
--- done:main(4)

The call stack

When a method call is initiated, a block of memory is allocated to handle this call. A block is allocated ("pushed") within a portion of memory called the run-time stack. In a simplistic sense, this block contains
method name
method parameters
where to go after completion
The word stack is suggestive of the allocation method: blocks are placed "on top of" each other. In the case of recursion, the call stack gets used very heavily. The building of the call stack is something like this:

message
4
"done-main"
message
n = 4
"done-main"
message
n = 3
"done-message"
message
n = 4
"done-main"
message
n = 3
"done-message"
message
n = 2
"done-message"
message
n = 4
"done-main"
message
n = 3
"done-message"
message
n = 2
"done-message"
message
n = 1
"done-message"
message
n = 4
"done-main"
message
n = 3
"done-message"
message
n = 2
"done-message"
message
n = 1
"done-message"
message
n = 0
"done-message"

When we reach the n = 0 call, it terminates (by skipping the if statement), the block is removed ("popped") from the stack and control transfers to "done-message" location using the n = 1 block. Next the message is printed:
-- done(0)
and the n = 1 call terminates, the block is popped, and control transfers again to "done-message" using the n = 1 block. This process continues, printing:
-- done:message(0)
-- done:message(1)
-- done:message(2)
-- done:message(3)
up to the very last block, with n = 4. When this call terminates control is transferred to "done-main", the final message
-- done:main(4)
is printed and the program terminates.

Recursive Problem-solving

This is section 16.2 in the textbook. The first section was meant to make you "believe in recursion." The harder part is what might be called "recursive thinking," or figuring out how to use recursion.

The factorial function

The factorial function is defined like this, for n > 0:
factorial(n) = the product of all integers ≤ n and > 0
In mathematics, it is often written using the notation:
n!
For example
factorial(6) = 6 * 5 * 4 * 3 * 2 * 1
This is easy enough to compute by iteration:
int result = 1;
for (int i = 1; i ≤ n; ++i) {
  result *= i;
}
We can think of the initial value "1" as what to use when n = 0, i.e., when no numbers are given, and so we'll also say:
factorial(0) = 1
Based on this, we can make a recurrence formula for factorial:
factorial(0) = 1
factorial(n) = n * factorial(n-1), for n > 0
From this we can write the recursive version:
FactorialDemo.java  
The Java code for the function is:
  private static int factorial(int n) {
    if (n == 0) {
      return 1;   // Base case
    }
    else {
      return n * factorial(n - 1);
    }
  }

More Examples

This is section 16.3 in the textbook.

Array Range Sum

The first thing we need to do is to correct the array range presentation in this (and other) Java textbooks. Java functions which deal with array ranges are consistently half-inclusive, meaning that the lower endpoint of the array range is included, but the upper end of the range is not included:
...fromfrom+1 ... to-1to...
Doing it this way makes the full array range more logical:
(0, array.length)
Also, it makes the array range size computation more simple:
size = to - from
Based on this idea here is a program comparing the iterative and recursive array sum computations:

ArraySum
import java.util.Arrays;
import java.util.Random;
 
public class ArraySum {
 
  public static void main(String[] args) {
    int[] nums = new int[7];
 
    Random rand = new Random();
 
    for (int i = 0; i < nums.length; i++) {
      nums[i] = rand.nextInt(10) + 1;
    }
 
    System.out.println(Arrays.toString(nums));
 
    int sumIter = arraySumIter(nums, 0, nums.length);
 
    int sumRec1 = arraySumRec1(nums, 0, nums.length);
 
    int sumRec2 = arraySumRec2(nums, 0, nums.length);
 
    System.out.println("iterative sum: " + sumIter);
 
    System.out.println("recursive sum1: " + sumRec1);
    System.out.println("recursive sum2: " + sumRec2);
  }
 
  static int arraySumIter(int[] array, int from, int to) {
    int sum = 0;
    for (int i = from; i < to; i++) {
      sum += array[i];
    }
    return sum;
  }
 
  // add from the bottom, increasing the from index
  static int arraySumRec1(int[] array, int from, int to) {
    if (from == to) {
      return 0;
    }
    else {
      return array[from] + arraySumRec1(array, from + 1, to);
    }
  }
 
  // add from the top, decreasing the to index
  static int arraySumRec2(int[] array, int from, int to) {
    if (from == to) {
      return 0;
    }
    else {
      return array[to-1] + arraySumRec2(array, from, to-1);
    }
  }
}
select

Concentric Circles

We cannot do this at this time.

Fibonacci Numbers

Here is the textbook version:
FibNumbers.java  
This is easier to write recursively than iteratively, except it's terribly inefficient written in this simple recursive way. Here is a comparison of the two versions. Once you get to the 40-th fibonacci number, or so, the recursive version really slows down. We've used long type to be able to compute values large enough to observe the speed comparison.

Fibonacci
public class Fibonacci {
 
  public static void main(String[] args) {
 
    int which = 45;
 
    long a = System.currentTimeMillis();  // mark time
 
    long fibNum1 = fib(which); // recursive
 
    long b = System.currentTimeMillis();  // mark time
 
    long fibNum2 = fibIter(which);  // iterative
 
    long c = System.currentTimeMillis();   // mark time
 
    // double-check that they compute the same thing
    System.out.println("fibNum1 = " + fibNum1);
    System.out.println("fibNum2 = " + fibNum2);
 
    System.out.printf("fib recursive time %s ms\n", b - a);
    System.out.printf("fib iterative time %s ms\n", c - b);
  }
 
  public static long fib(int n) {
    if (n < 2) {
      return n;
    }
    else {
      return fib(n - 1) + fib(n - 2);
    }
  }
 
  public static long fibIter(int n) {
    long save[] = new long[n+1];
    save[0] = 0;
    if (n > 0) {
      save[1] = 1;
    }
    for (int i = 2; i <= n; ++i) {
      save[i] = save[i-1] + save[i-2];
    }
    return save[n];
  }
}
select

Greatest Common Denominator

This could just as well be written iteratively, but the recursive version is cleaner. Unfortunately, to appreciate it you have to deal with the 4-letter word MATH!

MyGCDDemo
import java.util.Scanner;
 
public class MyGCDDemo {
  public static void main(String[] args) {
 
    Scanner keyboard = new Scanner(System.in);
 
    System.out.print("Enter two positive integers: ");
    int num1 = keyboard.nextInt();
    int num2 = keyboard.nextInt();
 
    System.out.printf("gcd(%d,%d) = %d\n", num1, num2, gcd(num1, num2));
  }
 
  public static int gcd(int x, int y) {
    System.out.printf("gcd(%d,%d)\n", x, y);
 
    int rem = x % y; // remainder
 
    // x = quot * y + rem, 0 <= rem < y
 
    if (rem == 0) {
      // y is a divisor of x
      return y;
    }
    else {
      return gcd(y, rem);
    }
  }
}
select
Try these inputs:
72 120

Recursive Binary Search

Even though this can be done iteratively, the recursive version is useful to understand. We must use a sorted array. First, let's look at Java's built-in binarySearch of arrays:

JavaBinarySearch
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;
 
public class JavaBinarySearch {
 
  public static void main(String[] args) {
 
    Random rand = new Random();
    Scanner keyboard = new Scanner(System.in);
 
    // generate a random array
    int[] searchArray = new int[15];
    for (int i = 0; i < searchArray.length; i++) {
      searchArray[i] = rand.nextInt(100) + 1;
    }
 
    // sort it
    Arrays.sort(searchArray);
 
    System.out.println(showIndices(searchArray));
 
    System.out.println(Arrays.toString(searchArray));
 
    System.out.print("enter search key: ");
 
    int key = keyboard.nextInt();
 
    int pos = Arrays.binarySearch(searchArray, 0, searchArray.length, key);
 
    // int pos = Arrays.binarySearch(searchArray, key); // Java equivalent
 
    if (pos >= 0) {
      System.out.printf("key %d found at position %d\n", key, pos);
    }
    else {
      System.out.printf("key %d not found, position = %s\n", key, pos);
    }
  }
 
  private static String showIndices(int[] array) {
    String output = " ";
    for (int i = 0; i < array.length; ++i) {
      int fieldlen = Integer.toString(array[i]).length();
      if (i > 0) {
        fieldlen += 2;
      }
      String format = "%" + fieldlen + "d";
      output += String.format(format, i);
    }
    return output;
  }
}
select
Note the call with the explicit range:
Arrays.binarySearch(int[] array, int from, int to, int key)
As we indicated earlier, the range is half-inclusive, meaning that the call to search the full array for key is:
Arrays.binarySearch(array, 0, array.length, key)
Now we'll imitate this. The algorithm uses a "divide-and-conquer" technique when searching for a key in the array within the range (from,to). We proceed as follows:
In diagrams, searching for key in array, within the given range:
from...mid ... to
Check array[mid] where mid = (from+to)/2:
from...mid
key?
If key < array[mid], search left half (excluding mid):
from...mid
If key > array[mid], search right half (excluding mid):
from...midmid+1 ...to

Here is the code:

MyBinarySearch
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;
 
public class MyBinarySearch {
 
  public static void main(String[] args) {
 
    Random rand = new Random();
    Scanner keyboard = new Scanner(System.in);
 
    // generate a random array
    int[] searchArray = new int[15];
    for (int i = 0; i < searchArray.length; i++) {
      searchArray[i] = rand.nextInt(100) + 1;
    }
 
    // sort it
    Arrays.sort(searchArray);
 
    // show the indices which correspond to values in searchArray
    System.out.println(showIndices(searchArray));
 
    System.out.println(Arrays.toString(searchArray));
 
    System.out.print("\nenter search key: ");
 
    int key = keyboard.nextInt();
    System.out.println();
 
    int pos = binarySearch(searchArray, 0, searchArray.length, key);
 
    if (pos >= 0) {
      System.out.printf("key %d found at position %d\n", key, pos);
    }
    else {
      System.out.printf("key %d not found, position = %s\n", key, pos);
    }
  }
 
  private static int binarySearch(int[] array, int from, int to, int key) {
    System.out.printf("binarySearch(%s,%s)\n", from, to);
    int size = to - from;
    if (size == 0) {
      return -from-1; 
    }
    int mid = (from + to)/2;
    if (key == array[mid]) { // found at position mid
      return mid;
    }
    else if (key < array[mid]) {  // search left half
      return binarySearch(array, from, mid, key);
    }
    else { // search right half
      return binarySearch(array, mid+1, to, key);
    }
  }
 
  private static String showIndices(int[] array) {
    String output = " ";
    for (int i = 0; i < array.length; ++i) {
      int fieldlen = Integer.toString(array[i]).length();
      if (i > 0) {
        fieldlen += 2;
      }
      String format = "%" + fieldlen + "d";
      output += String.format(format, i);
    }
    return output;
  }
}
select

Integer exponentiation

We want to write an algorithm to compute xn for an integer n ≥ 0. There is an obvious iterative way to do so:
  private static double powIter(double x, int n) {
    if (n == 0) {
      return 1;
    }
    double ans = x;
    for (int i = 1; i < n; ++i) {
      ans *= x;
    }
    return ans;
  }
Although we could make this algorithm recursive, we're going to find a more efficient way to do exponentiation. Consider computing:
powIter(x, 65);
This algorithm would require 64 multiplications. We can do a lot less. In fact, we can compute the answer with only 7 multiplications:
ans = x;
ans = ans * ans;  // x^2
ans = ans * ans;  // x^4
ans = ans * ans;  // x^8
ans = ans * ans;  // x^16
ans = ans * ans;  // x^32
ans = ans * ans;  // x^64
ans = ans * x;    // x^65
The basis of the more efficient algorithm we want is this:
n = 2 * n/2, if n even
n = 2 * n/2 + 1, if n odd
Recall that in Java, integer division truncates the decimal part, i.e., 5/2 = 2. Using properties of exponents, we can write these recurrence equations:
x0 = 1
x1 = x
for n > 1:
  n even: xn = (x2)n/2
  n odd:  xn = x * (x2)n/2
We can use the reduction in exponent to make a recursive function:
  public static double powRecur(double x, int n) {
    if (n == 0) {
      return 1;
    }
    if (n == 1) {
      return x;
    }
    if (n % 2 == 0) {
      return powRecur(x * x, n / 2);  // n even
    }
    else {
      return x * powRecur(x * x, n / 2); // n odd
    }
  }
Here is a test program which does both versions. We can add a gimmick to count the number of multiplications via an external variable.

IntegerExpon
public class IntegerExpon {
 
  public static void main(String[] args) {
    double ans1 = powIter(1.2, 65);
    double ans2 = powRecur(1.2, 65);
 
    System.out.printf("%.3f\n", ans1);
    System.out.printf("%.3f\n", ans2);
 
    System.out.println("multipCount = " + multipCount);
  }
 
  private static int multipCount = 0;
 
  private static double powIter(double x, int n) {
    if (n == 0) {
      return 1;
    }
    double ans = x;
    for (int i = 1; i < n; ++i) {
      ans *= x;
    }
    return ans;
  }
 
  public static double powRecur(double x, int n) {
    if (n == 0) {
      return 1;
    }
    if (n == 1) {
      return x;
    }
    if (n % 2 == 0) {
      multipCount += 1;
      return powRecur(x * x, n / 2);  // n even
    }
    else {
      multipCount += 2;      
      return x * powRecur(x * x, n / 2); // n odd
    }
  }
}
select

Towers of Hanoi

The textbook's version is correct, except you don't get to "see" the effects of the moves and confirm that the discs remain in order throughout the procedure.
Hanoi.java  
HanoiDemo.java  

Towers as Strings

You can use letters to represent the discs where a disc is "larger" if it lexicographically smaller (i.e. an "A" disc is less than a "B" disc). The discs on a peg represent a string from bottom to top and thus discs are in correct order if the letters in the string are in lexicographic order.

Moving a disc simply means taking the substring with the one character at the top, removing it from the string, and then concatenating it to the top of another string. Here is the code:

MyHanoi
public class MyHanoi {
 
  private static String[] pegs = {
    "ABC",  // peg0
    "",     // peg1
    "",     // peg2
  };
 
  public static void main(String[] args) {
    int numDiscs = pegs[0].length();
 
    System.out.println("peg0: " + pegs[0]);
    System.out.println("peg1: " + pegs[1]);
    System.out.println("peg2: " + pegs[2]);
    System.out.println("--------------");
 
    moveDiscs(numDiscs, 0, 2, 1);
  }
 
  private static final boolean VERBOSE_OUTPUT = true;
 
  private static void moveDiscs(int num, int fromPeg, int toPeg, int intermediate) {
    if (num > 0) {
 
      // move the top num-1 discs from fromPeg to intermediate
      moveDiscs(num - 1, fromPeg, intermediate, toPeg);
 
      int len = pegs[fromPeg].length();
 
      // move the remaining disc from fromPeg to toPeg
      if (!VERBOSE_OUTPUT) {
        System.out.printf("move disc from %d to %d\n", fromPeg, toPeg);
      }
      else {
        String top = pegs[fromPeg].substring(len - 1, len);   // only disc on fromPeg
        pegs[fromPeg] = pegs[fromPeg].substring(0, len - 1);  // remove it
        pegs[toPeg] += top;                                   // add it on toPeg
 
        System.out.println("peg0: " + pegs[0]);
        System.out.println("peg1: " + pegs[1]);
        System.out.println("peg2: " + pegs[2]);
        System.out.println("--------------");
      }
 
      // move the (entire) num-1 discs from intermediate to toPeg
      moveDiscs(num - 1, intermediate, toPeg, fromPeg);
    }
  }
}
select
The argument for why this works is inductive. An inductive argument starts with verifying the outcome for one or more base case.

Case n = 1

The first case is when the number of pegs is 1. We call:
moveDiscs(1, 0, 2, 1);  // move 1 disc from peg 0 to 2, with 1 as intermediate
The first recursive call does nothing:
moveDiscs(0, 0, 1, 2); // move 0 discs ...
Then move the one disc from peg 0 to peg 2, and the final recursive call also does nothing:
moveDiscs(0, 1, 2, 0);
For one disc, all moveDiscs(1,fromPeg,toPeg,intermediate) does is move the disc from fromPeg to toPeg, igoring the intermediate peg.

Case n = 2

We start like this:
peg0: AB
peg1:
peg2:
The initial call is:
moveDiscs(2, 0, 2, 1); // = moveDiscs(num, fromPeg, toPeg, intermediate)
The first recursive call is:
moveDiscs(1, 0, 1, 2); // = moveDiscs(num - 1, fromPeg, intermediate, toPeg)
We know that this simply moves the top disc on peg 0 to peg 1, getting:
peg0: A
peg1: B
peg2:
Then we move the only disc on peg 0 to peg 2, getting:
peg0:
peg1: B
peg2: A
We complete the operation by the second recursive call:
moveDiscs(1, 1, 2, 0); // = moveDiscs(num - 1, intermediate, toPeg, fromPeg);
The disc on peg 1 is moved to peg 2, getting the desired outcome:
peg0: 
peg1:
peg2: AB

General case

We want to prove the general case:

moveDiscs(n,fromPeg,toPeg,intermediate)
moves the top n discs from fromPeg to toPeg keeping them in order at all times

We have verified this for n = 1, 2. Suppose now that n > 2. We make the so-called "inductive assumption" and assume the general case is true for n - 1 discs. The point is then to prove it for n.

Let's make this a bit more concrete. Take n = 7 with this starting configuration:
peg0: ABCDEFG
peg1: 
peg2:
The call is:
moveDiscs(7, 0, 2, 1); // = moveDiscs(num, fromPeg, toPeg, intermediate)
The first recursive call is:
moveDiscs(6, 0, 1, 2); // = moveDiscs(num - 1, fromPeg, intermediate, toPeg)
By induction, this should work, getting:
peg0: A
peg1: BCDEFG
peg2:
Then move the only disc from peg 0 to peg 2, getting:
peg0:
peg1: BCDEFG
peg2: A
Finally, make the second recursive call:
moveDiscs(6, 1, 2, 0); // = moveDiscs(num - 1, intermediate, toPeg, fromPeg)
Again, by induction, this should work, getting the desired outcome:
peg0:
peg1: 
peg2: ABCDEFG

Navigating through a Maze

Like the Towers of Hanoi, solving this problem really needs recursion. Our maze is a two-dimensional array of 1's and 0's such that A path in this maze is a sequence of adjacent positions holding 0's where by adjacent we mean: In particular, positions on a diagonal are not adjacent. The goal is to find a path from the first (top) row to the last row.

The idea of how to explore such a maze is to mark your current position and then move from to an adjacent 0 in a methodical way: We can be blocked by either seeing a 1, or else seeing the earlier mark that we made. If we make even one step, we repeat the procedure until we are blocked in all directions.

Once we are blocked in all directions, we backtrack, going back one position at a time looking for other possible 0's to explore.

It is the notion of backtracking where recursion shows its strength. Each forward step is a recursive call. When we can no longer make a call, the recursive calls are "popped" from the stack along the current successful path, making the algorithm go back the way it came.

Our program illustrates the behavior we are describing by forcing the user to hit enter to move forward, or to backtrack out. If a path is found, this program will not explore any new paths, and will record the path backing out from the end position (in the last row) to the initial starting position.

Maze
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
 
public class Maze {
  private static Scanner keyboard = new Scanner(System.in);
 
  private static final int[][] MAZE = {
    {1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1},
    {1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
    {1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1},
    {1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1},
    {1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1},
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1},
  };
 
  public static void main(String[] args) {
    explore(0, 7);
    if (found) {
      System.out.println("Path Found: ");
      Collections.reverse(path);
      System.out.println(path);
    }
    else {
      System.out.println("No Path Found");      
    }
  }
 
  public static void printMaze(int row, int col) {
    for (int i = 0; i < MAZE.length; ++i) {
      for (int j = 0; j < MAZE[i].length; ++j) {
        int cell = MAZE[i][j];
        if (i == row && j == col) {
          System.out.print("o");
        }
        else if (cell == 0) {
          System.out.print(" ");
        }
        else if (cell == 1) {
          System.out.print("*");
        }
        else if (cell == 2) {
          System.out.print("+");
        }
      }
      System.out.println();
    }
    System.out.println("-------------------");
  }
 
  public static void show_wait(int row, int col) {
    printMaze(row, col);
    keyboard.nextLine();
  }
 
  private static boolean found = false;
 
  private static ArrayList<String> path = new ArrayList();
 
  public static void explore(int row, int col) {
 
    if (found) { // don't look for any new paths
      return;
    }
 
    // mark position as seen
    MAZE[row][col] = 2;
 
    show_wait(row, col);
 
    if (row + 1 == MAZE.length) { // beyond number of rows
      found = true;               // a path is found
      System.out.println("--- path found ---");
      return;
    }
    if (MAZE[row + 1][col] == 0) { // try down
      explore(row + 1, col);
    }
    if (MAZE[row][col - 1] == 0) { // try left
      explore(row, col - 1);
    }
    if (MAZE[row][col + 1] == 0) { // try right
      explore(row, col + 1);
    }
    if (row != 0 && MAZE[row - 1][col] == 0) { // try up
      explore(row - 1, col);
    }
 
    // this shows backing out of recursive calls
    show_wait(row, col);
 
    // track the path as come out of explore calls
    if (found) {
      path.add(String.format("(%d,%d)",row,col));
      System.out.printf("--- record position (%d,%d)\n", row, col);
    }
  }
}
select


© Robert M. Kline