//  Data Structures with Java by John R. Hubbard
//  Copyright McGraw-Hill, 2001
//  Problem 4.07 on page 85
//  Recursive Function that returns nth power of x
//    and makes no more than lgn recursive calls
public class Pr0407
{ public static void main(String[] args)
  { double x ;
    int n ;
    int power ;
    for ( int count = 0 ; count < 10 ; count++ )
    {  x =  Math.round(Math.random()*10.0) ;
       n =  (int)(Math.round(Math.random()*10));
       System.out.println("pow("+x+","+n+") = " + pow(x,n) );
    }  
  }
  public static double pow(double x, int n)
  { if (n==0) return 1.0;    // basis
    double p =pow(x,n/2) ;
    if ( n%2 == 0 ) return p*p ; // recursion (n even)
    else return  x*p*p ;         // recursion (n odd)
  }
}