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.
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.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 );
}
We see that Prime
has two base cases and one recursive call.
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.
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.
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.