7.4. 编写更复杂的递归函数
某些递归函数只有一个基本情况和一次递归调用。但通常存在多于一个基本情况或一次递归调用，或者两者皆有。
以下是递归函数的通用结构。
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
考虑一个相对简单的函数，用于判断整数 X Y 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 );
}
我们看到， Prime
Example 7.4.2
这里有一个具有多个递归调用的函数。给定一个名为 set int isSubsetSum set sum sum = 4 true sum = 6 true \(8 + 1 + -3 = 6\) 。另一方面，如果 sum = 2 false n set.length
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 ] );
}
本例有两个基本情况和两个递归调用。
Example 7.4.3
此处有一个函数，它包含多个基本情况和多个递归调用。函数 paths n = 3 paths \(1+1+1, 1+2, 2+1,\) 和 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 );
}
该函数具有三个基本情况和三个递归调用。
