title: Calculating power function in logn time and constant space
body: <p>This question I encountered while giving the interview. 
  Lets say I wanted to calculate power(x, n)  which is x^n.</p>
  
  <p>The best algorithm I know is calculating pow(x, n) in O(logn) time but that is a recursive algorithm which takes O(logn) space (Call stack).</p>
  
  <pre><code>int pow(int x, int n)
  {
     if(n==0)
        return 1;
  
     int tmp = pow(x,n/2);
  
     if(n%2)
       return tmp*tmp*x;
  
     return tmp*tmp;
  }
  </code></pre>
  
  <p>Above algorithm runs in O(logn) time but its call stack taking O(logn) space.
  How do I make the space constant while keeping the O(logn) time.</p>
  
  <p>The algorithm which I can think as of now takes O((logn)^2) time but in constant space (converting the above algorithm iterative and calculating pow in terms of 2^i). 
  Can we achieve the bound to O(logn) time and constant space?</p>