title: Algorithm to calculate exponent using recursion and mod
body: <p>I was taught a different way to calculate exponents using mod and recursion, but I don't fully understand it. The method is: To do <code>b^e</code>, we can break it down like so: </p>
  
  <pre><code>  q = e div 2
    r = e mod 2
  then e = 2q+r, and r could be 0 or 1.
  
  If r=0:
  
      b^e = (b^q)^2
  
  If r=1:
  
      b^e = (b^q)^2 * b
  
  base case: b^0 = 1.
  </code></pre>
  
  <p>For example: <code>2^2, b=2, e=2</code>.</p>
  
  <pre><code>q = 2/2 = 1
  r = 2mod2 = 0
  
  r=0, therefore 2^2 = 2^1^2
  </code></pre>
  
  <p>I am trying to code this. </p>
  
  <pre><code>pow :: Integer -&gt; Integer -&gt; Integer
  pow b e
      | e == 0 = 1
      | r == 0 = pow (pow b q) 2
      | r == 1 = b * pow (pow b q) 2
    where
      (q, r) = divMod e 2
  </code></pre>
  
  <p>But the code does not end any time when <code>e!=0</code>, for example, <code>pow (-2) 4</code> or <code>pow 1 1</code> goes on forever. Any idea why?</p>