адача 3. Пусть a - вещественное число отличное от нуля и n - целое неотрицательное число. Составить рекурсивную программу-функцию, возвращающую величину aⁿ.

Решение. Приведенная ниже функция power(a,n) дает решение задачи за n рекурсивных вызовов:

Уменьшить количество вызовов можно так. Организуем декомпозицию иначе, представив величину aⁿ в виде:

Отсюда сразу же получаем алгоритм вычисления aⁿ, требующий не более чем log₂(n) рекурсивных вызовов. Реализуется он функцией pow(a,n):

Функция powe(n) также вычисляет aⁿ не более чем за log₂(n) рекурсивных вызовов: