10.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 10.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
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 (Y == 1)
return true;
else if (X % Y == 0)
return false;
else
return Prime(X, Y-1);
}
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 (Y == 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 10.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.
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]);
}
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 10.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.
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);
}
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.
