Recursive Binary Exponentiation by fast doubling.

exbin.cc

#include <iostream>
using namespace std;

int expbin(int a, int e, int m, int acc) {
  if (e == 0) return acc;
  if (e % 2 == 1) return expbin(a, e-1, m, (acc * a) % m);
  return expbin((a * a) % m, e/2, m, acc);
}


int main() {
  for(int i = 0; i < 10; ++i) {
    cout << "2**"<<i<< " = " << expbin(2, i, 100000, 1) << "\n";
  }
  return 0;
}

Objetivo deste exemplo é mostrar como um código recursivo pode ser transformado para se beneficiar da recursão na cauda (tail call).