Викиучебник

Основы функционального программирования/Структуры данных и базисные операции — 2: различия между версиями

Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Строка 113:
=== Накапливающий параметр — аккумулятор ===
 
Бывает так, что при выполнении функции исключительно серьезно встаетвстаёт проблема расхода памяти. Эту проблему можно пояснить на примере функции, вычисляющей факториал числа:
 
<math>Factorial (0) = 1</math>
Factorial (N) = N * Factorial (N – 1)▼
 
▲ <math>Factorial (N) = N * Factorial (N – 1)</math>
Если провести пример вычисления этой функции с аргументом 3, то можно будет увидеть следующую последовательность:▼
 
▲Если провести пример вычисления этой функции с аргументом <math>3</mat>, то можно будет увидеть следующую последовательность:
Factorial (3)
 
==> 3 * Factorial (2)
==<math> 3 * 2 * Factorial (13)</math>
 
==> 3 * 2 * 1 * Factorial (0)▼
<tt>==></tt> <math>3 * Factorial(2 * 1 * 1)</math>
 
==> 3 * 2 * 1
<tt>==></tt> <math>3 * 2 * Factorial(1)</math>
==> 3 * 2
 
==> 6
▲ <tt>==></tt> <math>3 * 2 * 1 * Factorial (0)</math>
 
<tt>==></tt> <math>3 * 2 * 1 * 1</math>
 
<tt>==></tt> <math>3 * 2 * 1</math>
 
<tt>==></tt> <math>3 * 2</math>
 
<tt>==></tt> <math>6</math>
 
На примере этого вычисления наглядно видно, что при рекурсивных вызовах функций очень сильно используется память. В данном случае количество памяти пропорционально значению аргумента, но аргументов может быть большее число, к примеру. Возникает резонный вопрос: можно ли так написать функцию вычисления факториала (и ей подобные), чтобы память использовалась минимально?
 
Чтобы ответить на данный вопрос положительно, необходимо рассмотреть понятие аккумулятора (накопителя). Для этого можно рассмотреть следующий пример:
 
'''Пример 10. Функция вычисления факториала с аккумулятором.'''
 
<math>Factorial_A (N) = F (N, 1)</math>
 
<math>F(0, A) = A</math>
 
<math>F (0N, A) = F((N – 1), (N * A))</math>
F (N, A) = F ((N – 1), (N * A))
 
В этом примере второй параметр функции <math>F</math> выполняет роль аккумулирующей переменной, именно в ней содержится результат, который возвращается по окончании рекурсии. Сама же рекурсия в этом случае принимает вид «хвостовой», память при этом расходуется только на хранение адресов возврата значения функции.
 
Хвостовая рекурсия представляет собой специальный вид рекурсии, в которой имеется единственный вызов рекурсивной функции и при этом этот вызов выполняется после всех вычислений.
 
При реализации вычисления хвостовой рекурсии могут выполняться при помощи итераций в постоянном объемеобъёме памяти. На практике это обозначает, что «хороший» транслятор функционального языка должен «уметь» распознавать хвостовую рекурсию и реализовывать её в виде цикла. В свою очередь, метод накапливающего параметра не всегда приводит к хвостовой рекурсии, однако он однозначно помогает уменьшить общий объём памяти.
 
=== Принципы построения определений с накапливающим параметром ===
 
#Вводится новая функция с дополнительным аргументом (аккумулятором), в котромкотором накапливаются результаты вычислений.
#Начальное значение аккумулирующего аргумента задается в равенстве, связывающем старую и новую функции.
#Те равенства исходной функции, которые соответствуют выходу из рекурсии, заменяются возвращением аккумулятора.
Строка 164 ⟶ 174 :
При этом на выражения <math>e_{ij}</math> накладываются следующие ограничения:
 
#eij<math>e_{ij}</math> — «простое» выражение, т.&nbsp;е. оно не содержит рекурсивных вызовов, а только операции над данными.
#eij<math>e_{ij}</math> имеет вид fk <math>f_{k}(vkv_{k})</math>, при этом vk<math>v_{k}</math> — последовательность простых выражений. Это и есть хвостовая рекурсия.
#eij<math>e_{ij}</math> — условное выражение с простым выражением в условии, ветви которого определяются этими же тремя пунктами.
 
== Упражнения ==
Источник — https://ru.wikibooks.org/wiki/Основы_функционального_программирования/Структуры_данных_и_базисные_операции_—_2