7.4. Writing More Sophisticated Recursive Functions¶

Some recursive functions have only one base case and one recursive call. But it is common for there to be more than one of either or both.

The following is the general structure for a recursive function.

Java (Generic)
Java

if ( base case 1 ) {
  // return some simple expression
}
else if ( base case 2 ) {
  // return some simple expression
}
else if ( base case 3 ) {
  // return some simple expression
}
else if ( recursive case 1 ) {
  // some work before 
  // recursive call 
  // some work after 
 }
else if ( recursive case 2 ) {
  // some work before 
  // recursive call 
  // some work after 
 }
else { // recursive case 3 
  // some work before 
  // recursive call 
  // some work after 
 }

if ( base case 1 )
  // return some simple expression
else if ( base case 2 )
  // return some simple expression
else if ( base case 3 )
  // return some simple expression
else if ( recursive case 1 ) {
  // some work before 
  // recursive call 
  // some work after 
 }
else if ( recursive case 2 ) {
  // some work before 
  // recursive call 
  // some work after 
 }
else { // recursive case 3 
  // some work before 
  // recursive call 
  // some work after 
 }

Example 7.4.2

Here is a function that has multiple recursive calls. Given an int array named set, function isSubsetSum determines whether some of the values in set add up to sum. For example, given the numbers 3, 8, 1, 7, and -3, with sum = 4, the result is true because the values 3 and 1 sum to 4. If sum = 6, then the result will be true because the \(8 + 1 + -3 = 6\). On the other hand, if sum = 2 then the result is false there is no combination of the five numbers that adds up to 2. In this code, variable n is the number of values that we look at. We don’t want to just use set.length because the recursive calls need to limit their work to part of the array.

Java (Generic)
Java
C++

boolean isSubsetSum(int set[], int n, int sum) {
  if (sum == 0) {
    return true;
  }
  if ((n == 0) && (sum != 0)) {
    return false;
  }
  return isSubsetSum(set, n - 1, sum) || isSubsetSum(set, n - 1, sum - set[n - 1]);	
}

boolean isSubsetSum(int set[], int n, int sum) {
  if (sum == 0)
    return true;
  if ((n == 0) && (sum != 0))
    return false;
  return isSubsetSum(set, n - 1, sum) || isSubsetSum(set, n - 1, sum - set[n - 1]);	
}

boolean isSubsetSum(int set[], int n, int sum) {
  if (sum == 0)
    return true;
  if ((n == 0) && (sum != 0))
    return false;
  return isSubsetSum(set, n - 1, sum) || isSubsetSum(set, n - 1, sum - set[n - 1]);
}

This example has two base cases and two recursive calls.

Example 7.4.3

Here is a function that has multiple base cases and multiple recursive calls. Function paths counts the number of different ways to reach a given basketball score. Recall that in Basketball, it is possible to get points in increments of 1, 2, or 3. So if n = 3, then paths will return 4, since there are four different ways to accumulate 3 points: \(1+1+1, 1+2, 2+1,\) and 3.

Java (Generic)
Java
C++

int paths(int n) {
  if (n == 1) {
    return 1;
  }
  if (n == 2) {
    return 2;
  }
  if (n == 3) {
    return 4;
  }
  return paths(n - 1) + paths(n - 2) + paths(n - 3);
}

int paths(int n) {
  if (n == 1)
    return 1;
  if (n == 2)
    return 2;
  if (n == 3)
    return 4;
  return paths(n - 1) + paths(n - 2) + paths(n - 3);
}

int paths(int n) {
  if (n == 1)
    return 1;
  if (n == 2)
    return 2;
  if (n == 3)
    return 4;
  return paths(n - 1) + paths(n - 2) + paths(n - 3);
}

This function has three base cases and three recursive calls.

CS2 Software Design & Data Structures

Chapter 7 Recursion

7.4. Writing More Sophisticated Recursive Functions¶