title: Computing integer powers with a recursive divide-and-conquer algorithm
body: <p>I have implemented a recursive function to find m^n (m raised to the power n).</p>
  
  <p>Now I want to implement the same function but by dividing the problem into two equal parts, like</p>
  
  <p><code>m^n = m^(n/2) * m^(n/2) = ...</code> (for even n like, m^2, m^4, m^6).</p>
  
  <p>With the implementation below, if I give m = 2 and n = 4, my output is <strong>4</strong> while it should be <strong>16</strong>.</p>
  
  <pre><code>public class Recursion {
  
    public static void main(String[] args) {
      System.out.println(pow(2, 4));
    }
  
    public static long pow(long m,long n) { 
      if (n &gt; 0)
        return m * pow(m, ((n/2) - 1) * pow(m, ((n/2) - 1)));
      else
        return 1;
    }
  
  }
  </code></pre>