logo

APSU Notes


Recursion

Savitch 11.1-11.2

Topics

11.1 – The Basics of Recursion

The Basics of Recursion

  • A recursive algorithm is an algorithm with a subtask that is similar to the entire task.
  • A recursive method implements a recursive algorithm by calling itself.
  • A recursive call is the part of a recursive method where it calls itself.
  • A recursive method must have a base case that does not contain any recursive calls.
  • Algorithm: count down from a number num.
    • Base case: if num is less than or equal to zero, display a newline.
    • Recursive case: otherwise display num and count down from num - 1.

Recursive Method Implementation



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



public class RecursiveCountdown {

  public static void main(String[] args) {
    countDown(3);
  }

  public static void countDown(int num) {
    if (num <= 0) {   // base case
      System.out.println();
    }
    else {
      System.out.print(num);
      countDown(num - 1);  // recursive call
    }
  }

}

Digits to Words

  • Algorithm: display the digits of a number as words.
      1. Display all digits but the last one as words.
      1. Display the last digit as a word.
  • The first subtask is similar to the entire task, so it can be performed with a recursive call.
  • The second task can be accomplished using a separate method.


1
2
3
4



public static void displayAsWords(int number) {
  displayAsWords(number / 10);
  System.out.print(getWordFromDigit(number % 10) + " ");
}
  • This does not handle the case where the number is a single digit.

Digits to Words Implementation



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23



public static getWordFromDigit(int digit) { // precondition: 0 <= digit <= 9
  String result = null;
  switch (digit)
  {
     case 0: result = "zero"; break;
     case 1: result = "one"; break;
     ...
     case 9: result = "nine"; break;
     default: // number is not a single digit
       System.out.println("Fatal Error.");
       System.exit(0);
  }
  return result;
}

public static void displayAsWords(int number) {
  if (number < 10) // number is a single digit
    System.out.print(getWordFromDigit(number) + " ");
  else {
    displayAsWords(number / 10); // recursively display all but last digit
    System.out.print(getWordFromDigit(number % 10) + " "); // display last digit
  }
}

How Recursion Works

  • A recursive call works the same way as a regular method call.
  • Example:


1
2
3
4
5
6



displayAsWords(987):
  displayAsWords(98):
    displayAsWords(9):
      System.out.print(getWordFromDigit(9)); // displays nine
    System.out.print(getWordFromDigit(8)) // displays eight
  System.out.print(getWordFromDigit(7)) // displays seven
  • Keys to successful recursion:
    • Use an if-else or other branching statement that leads to different cases.
    • One or more branches must contain a base case with no recursive call.
    • One or more branches must contain a recursive call.
    • The recursive call must perform a “smaller” version of the task.

Infinite Recursion

  • Consider the first version of displayAsWords.


1
2
3
4



public static void displayAsWords(int number) {
  displayAsWords(number / 10);
  System.out.print(getWordFromDigit(number % 10) + " ");
}
  • If this is called with 987 as an argument, it never terminate:


1
2
3
4
5



 displayAsWords(987):
  displayAsWords(98):
    displayAsWords(9):
      displayAsWords(0):
        displayAsWords(0): ...
  • This is an example of infinite recursion, which can generate a stack overflow error.

Recursive Methods Versus Iterative Methods

  • Any method with a recursive call can be rewritten to perform the same task without recursion.


1
2
3
4
5
6
7
8
9
10



public static void displayAsWords(int number) {
  int divisor = getPowerOfTen(number);
  int next = number;
  while(divisor >= 10) {
    System.out.print(getWordFromDigit(next / divisor) + " ");
    next = next % divisor;
    divisor = divisor / 10;
  }
  System.out.print(getWordFromDigit(next / divisor) + " ");
}

Additional Methods



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



// precondition: n >= 0
public static int getPowerOfTen(int n) {
  int result = 1;
  while (n >= 10) {
    result = result * 10;
    n = n / 10;
  }
  return result;
}

// precondition: 0 <= digit <= 9
public static getWordFromDigit(int digit) {
  // same as before
}

Recursive Methods That Return a Value

  • If a recursive method returns a value, it can be computed using the return values of the recursive calls.


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



public static int getNumberOfZeros(int n) {
  int result;
  if (n == 0)            // last digit is zero, no more digits
    result = 1;
  else if (n < 10)       // last digit is not zero, no more digits
    result = 0;
  else if (n % 10 == 0)  // last digit is zero, more digits
    result = getNumberOfZeros(n / 10) + 1;
  else                   // last digit is not zero, more digits
    result = getNumberOfZeros(n / 10);
  return result;
}
  • Example:


1
2
3
4
5
6
7
8
9



getNumberOfZeros(2020):
  result = getNumberOfZeros(202) + 1:
    result = getNumberOfZeros(20):
      result = getNumberOfZeros(2) + 1:
        result = 0
        return 0
      return 1 // getNumberOfZeros(2) + 1 = 0 + 1 = 1
    return 1 // getNumberOfZeros(20) = 1
  return 2 // getNumberOfZeros(202) + 1 = 1 + 1 = 2

11.2 – Programming with Recursion

Recursive Input Validation

  • Input validation can be performed by a recursive method:


1
2
3
4
5
6
7
8
9
10
11



// Get a positive integer from the user
public int getCount() {
  System.out.println("Enter a positive integer: ");
  Scanner keyboard = new Scanner(System.in);
  count = keyboard.nextInt();
  if (count <= 0) {
    System.out.println("Input must be positive. Try again.");
    getCount() // starts the method over again
  }
  return count;
}
  • The sequential search algorithm finds the location of an item in an array by checking each element in order.
  • If the contents of an array are in sorted order, a binary search algorithm can be used to find an item in less time.
  • A binary search starts looking in the middle of the array and repeatedly eliminates half of the elements until the item is found.
  • Given an item target and range of array indexes starting at first and ending at last, a binary search does the following:
    1. Set midto the midpoint between first and last.
    2. If there are no items in the range, return -1.
    3. If target == the item at mid, return mid.
    4. If target < the item at mid, return the result of a search from first to mid - 1.
    5. If target > the item at mid, return the result of a search from mid + 1 to last.

Binary Search Implementation



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



// Should be called initially as binarySearch(arr, target, 0, arr.length – 1)
private static int binarySearch(int[] arr, int target, int first, int last) {
  int result = -1;
  if (first <= last) {           // the range is not empty
    int mid = (first + last) / 2;
    if (target == arr[mid])      // CASE 1: target is found
      result = mid;
    else if (target < arr[mid])  // CASE 2: the target must come before mid
      result = binarySearch(arr, target, first, mid – 1);
    else                         // CASE 3: the target must come after mid
      result = binarySearch(arr, target, mid + 1, last);
  }
  return result;
}

Binary Search Example

binarysearchexample

Merge Sort

  • The selection sort algorithm sorts an array by repeatedly finding the smallest unsorted item and moving it to its correct position.
  • The merge sort algorithm sorts more efficiently by dividing the array in half, sorting the halves, then merging the results.
  • Given an array, merge sort does the following:
    1. If the array has only one element do nothing, otherwise do the following:
    2. Copy the first half of the elements into a smaller array.
    3. Copy the second half of the elements into another smaller array.
    4. Sort the first half array using a recursive call.
    5. Sort the second half using a recursive call.
    6. Merge the elements of the two halves back into the original array.

Merge Sort Implementation



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39



// class containing a public static sort method and private static helpers
public class MergeSort {

// divide items in array into firstHalf and last Half
  private static void divide(int[] arr, int[] firstHalf, int[] lastHalf) {
    for (int i = 0; i < firstHalf.length; i++) // copy first half
      firstHalf[i] = arr[i];
    for (int i = 0; i < lastHalf.length; i++)  // copy last half
      lastHalf[i] = arr[firstHalf.length + i];
  }

  // merge items from firstHalf and lastHalf into arr
  private static void merge(int[] arr, int[] firstHalf, int[] lastHalf) {
    int i = 0, j = 0, k = 0;       // indexes for for arr, firstHalf, and lastHalf
    while(j < firstHalf.length && k < lastHalf.length)
      if (firstHalf[j] < lastHalf[k])
        arr[i++] = firstHalf[j++]; // copy item from firstHalf, increment indexes
      else
        arr[i++] = lastHalf[k++];  // copy item from lastHalf, increment indexes
    while(j < firstHalf.length)    // items left over in firstHalf
      arr[i++] = firstHalf[j++];
    while(k < lastHalf.length)     // items left over in lastHalf
      arr[i++] = lastHalf[k++]
  }

  // sort the array using the merge sort algorithm
  public static void mergeSort(int [] arr) {
    if (arr.length >= 2) { // at least 2 elements in the array
      int halfLength = arr.length / 2;
      int[] firstHalf = new int[halfLength];
      int[] lastHalf = new int[arr.length – halfLength]; // in case length is odd

      divide(arr, firstHalf, lastHalf); // split arr into two halves
      sort(firstHalf); // recursively sort first half
      sort(lastHalf); // recursively sort last half
      merge(arr, firstHalf, lastHalf); // merge halves into arr
    }
  }
}

Merge Sort Example



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



MergeSort.sort({44, 31, 73, 88, 12, 55, 63, 27}):
  sort({44, 31, 73, 88}):
    sort({44, 31}):
      merge(arr, {44}, {31})          // arr: {44, 31}
    sort({73, 88}):
      merge(arr, {73}, {88})          // arr: {73: 88}
    merge(arr, {31, 44}, {73, 88})    // arr: {33, 44, 73, 88}
  sort({12, 55, 63, 27}):
    sort({12, 55}):
      merge(arr, {12}, {55})          // arr: {12, 55}
    sort({63, 27}):
      merge(arr, {63}, {27})          // arr: {27, 63}
    merge(arr, {12, 55}, {27, 63})    // arr: {12, 27, 55, 63}
  merge(arr, {31, 44, 73, 88}, {12, 27, 55, 63})
                                      // arr: {12, 27, 31, 44, 55, 63, 73, 88}

Chapter 11 Summary

  • If a method definition includes an invocation of the method itself, that invocation is known as a recursive call. Recursive calls are legal in Java and can sometimes make a method definition clearer.
  • Whenever an algorithm has one subtask that is a smaller version of the entire algorithm’s task, you can realize the algorithm as a Java recursive method.
  • To avoid infinite recursion, a recursive method definition should contain two kinds of cases: one or more cases that include a recursive call and one or more base (stopping) cases that do not involve any recursive calls.
  • Two good examples of recursive algorithms are the binary search algorithm and the merge sort algorithm.
  • A lambda function is a nameless function that allows you to quickly implement a method.

Powerpoint

View presentation

Quiz

Quiz 6, Quiz 10