Вариант 4. Быстрое возведение в степень: pow(a, n) = 1, если n = 0; a · pow(a, n−1), а затем оптимизировать до O(log n).

Чтобы получить сложность O(log n), используем деление показателя пополам. Предполагается, что n — целое неотрицательное число.

1. База: если n = 0, возвращаем 1.
2. Рекурсивно вычисляем t = pow(a, ⌊n/2⌋).
3. Если n чётное, возвращаем t · t; если нечётное — a · t · t.

За один вызов показатель уменьшается примерно вдвое, поэтому число вызовов пропорционально log n.

Ответ: pow(a,n) = 1 при n = 0; иначе t = pow(a, ⌊n/2⌋), результат — t² при чётном n и a·t² при нечётном n.