На этом шаге мы определим дальнейшие действия.

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

Степенная функция

Классическая задача для иллюстрации рекурсии - степенная функция. Цель состоит в том, чтобы вычислить b в степени n:

        _n
   bⁿ = ∏ b = b * b * ... * b 
       ⁱ⁼¹            ^{n раз}

где основание степени b - вещественное число, а её показатель (экспонента) n - неотрицательное целое число (в Python степень вычисляется операцией **). Последующие шаги исследуют алгоритмы вычисления степени за линейное и логарифмическое время.

На следующем шаге мы рассмотрим вычисление степени за линейное время.

Предыдущий шаг Содержание Следующий шаг