Накапливающий параметр — аккумулятор

Бывает так, что при выполнении функции исключительно серьезно встает проблема рас­хода памяти. Эту проблему можно пояснить на примере функции, вычисляющей фак­то­риал числа:

Factorial (0) = 1

Factorial (N) = N * Factorial (N – 1)

Если провести пример вычисления этой функции с аргументом 3, то можно будет уви­деть следующую последовательность:

Factorial (3)

3 * Factorial (2)

3 * 2 * Factorial (1)

3 * 2 * 1 * Factorial (0)

3 * 2 * 1 * 1

3 * 2 * 1

3 * 2

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

Чтобы ответить на данный вопрос положительно, необходимо рассмотреть понятие аккумулятора (накопителя). Для этого можно рассмотреть следующий пример:

Пример 3.3. Функция вычисления факториала с аккумулятором.

Factorial_A (N) = F (N, 1)

F (0, A) = A

F (N, A) = F ((N – 1), (N * A))

В этом примере второй параметр функции F играет роль аккумулирующей пе­ре­мен­ной, именно в ней содержится результат, который возвращается по окончании ре­кур­сии. Сама же рекурсия в этом случае принимает вид "хвостовой", память при этом рас­хо­ду­ется только на хранение адресов возврата значения функции.

Хвостовая рекурсия представляет собой специальный вид рекурсии, в которой имеется един­ственный вызов рекурсивной функции и при этом этот вызов выполняется после всех вы­числений.

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