第5章递归与广义表 float RecurveArray∷ Average(intn){∥递归求数组的平均值 else return((float)Elements[n-1]+(n-1)* Average(n-1))/n int main( int arge, char argv [)i InputArrayo <<"nThe max is: "< ra MaxKey( ra MaxSize )< endl cout<<"nthe avr is: "<< ra. Average( ra MaxSize )<<endl; 5-2已知 Ackerman函数定义如下 当m=0时 akm(m,n)=akm(m-1,1) 当m≠0,n=0时 akmm-1,am(m,n-1)当m≠0n≠0时 (1)根据定义,写出它的递归求解算法 (2)利用栈,写出它的非递归求解算法 【解答】 (1)已知函数本身是递归定义的,所以可以用递归算法来解决 unsigned akm( unsigned m, unsigned n)i f(m==0) return n+l: else if(n==0)return akm( m-1, 1); ∥m>0,n=0 else return akm( m-l, akm( m, n-1)); ∥m>0.n>0 (2)为了将递归算法改成非递归算法,首先改写原来的递归算法,将递归语句从 结构中独立出来 unsigned akm( unsigned m, unsigned n )i f(m==0) return n+l: if (n==o)return akm( m-1, 1); ∥m>0,n==0 v= akm(m, n-1)); ∥m>0,n>0 return akm( m-l, v)第 5 章 递归与广义表 54 float RecurveArray :: Average ( int n ) { //递归求数组的平均值 if ( n == 1) return (float) Elements[0]; else return ( (float) Elements[n-1] + ( n - 1) * Average ( n - 1 ) ) / n; } int main ( int argc, char* argv [ ] ) { int size = -1; cout << "No. of the Elements : "; while ( size < 1 ) cin >> size; RecurveArray ra ( size ); ra.InputArray(); cout<< "\nThe max is: " << ra.MaxKey ( ra.MaxSize ) << endl; cout<< "\nThe sum is: " << ra.Sum ( ra.MaxSize ) << endl; cout<< "\nthe avr is: " << ra.Average ( ra.MaxSize ) << endl; return 0; } 5-2 已知 Ackerman 函数定义如下： akm m n n m akm m m n akm m akm m n m n ( , ) ( , ) , ( , ( , )) , = + = −  = − −        1 0 1 1 0 0 1 1 0 0 当 时 当 时 当 时 (1) 根据定义，写出它的递归求解算法； (2) 利用栈，写出它的非递归求解算法。 【解答】 (1) 已知函数本身是递归定义的，所以可以用递归算法来解决： unsigned akm ( unsigned m, unsigned n ) { if ( m == 0 ) return n+1; // m == 0 else if ( n == 0 ) return akm ( m-1, 1 ); // m > 0, n == 0 else return akm ( m-1, akm ( m, n-1 ) ); // m > 0, n > 0 } (2) 为了将递归算法改成非递归算法，首先改写原来的递归算法，将递归语句从 结构中独立出来： unsigned akm ( unsigned m, unsigned n ) { unsigned v; if ( m == 0 ) return n+1; // m == 0 if ( n == 0 ) return akm ( m-1, 1 ); // m > 0, n ==0 v = akm ( m, n-1 ) ); // m > 0, n > 0 return akm ( m-1, v );