8.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.

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 8.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.

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.

CSCD 320 Algorithms (Java)

Chapter 8 Recursion

8.4. Writing More Sophisticated Recursive Functions¶