3.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 3.4.1

Consider a rather simple function to determine if an integer X is prime or not. Y is a helper variable that is used as the devisor. When calling the function initially, Y = X - 1

Java
C++

boolean prime(int x, int y) {
  if (y == 1)
    return true;
  else if (x % y == 0)
    return false;	
  else
    return prime(x, y-1);
}

boolean prime(int x, int y) {
  if (x == 1)
    return true;
  else if (x % y == 0)
    return false;	
  else
    return prime(x, y-1);
}

We see that Prime has two base cases and one recursive call.

Example 3.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 number 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
C++

boolean isSubsetSum(int set[], int n, int sum) {
  if (sum == 0)
    return true;
  if ((n == 0) && (sum != 0))
    return false;
  if (set[n - 1] > sum)
    return isSubsetSum(set, n - 1, sum);
  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;
  if (set[n - 1] > sum)
    return isSubsetSum(set, n - 1, sum);
  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 3.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
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);
}

This function has three base cases and three recursive calls.

Data Structures and Algorithms Y

Chapter 3 Recursion

3.4. Writing More Sophisticated Recursive Functions¶