Consider the following definition of a recursive function,
power, that will perform exponentiation.
int power( int b, int e )
{
if( e == 0 ) return 1;
if( e % 2 = 0 ) return power( b * b, e/2 );
return b * power( b * b, e/2 );
}
Asymptotically in terms of the exponent e, the number of
calls to power that occur as a result of the call power(b,e)
is