Похоже на бесконечную рекурсию.
Да нет тут никакой бесконечной рекурсии: второй аргумент функции уменьшается минимум наполовину при каждом рекурсивном вызове.
Программа работает, но не могу понять как.
Это быстрое возведение в степень. Например,

вычисляется как

Только лучше убрать лишние вызовы: заменить
Код:
x=power3(x, n/2)*power3(x, n/2);
на что-то типа
Код:
{ int p = power3(x, n/2); x = p*p; }