Принципы построения определений с накапливающим параметром

1. Вводится новая функция с дополнительным аргументом (аккумулятором), в котором на­капливаются результаты вычислений.

2. Начальное значение аккумулирующего аргумента задается в равенстве, связывающем ста­рую и новую функции.

3. Те равенства исходной функции, которые соответствуют выходу из рекурсии, за­ме­ня­ют­ся возвращением аккумулятора.

4. Равенства, соответствующие рекурсивному определению, выглядят как обращения к но­вой функции, в котором аккумулятор получает то значение, которое возвращается ис­ходной функцией.

Возникает вопрос: любую ли функцию можно преобразовать для вычисления с ак­ку­му­ля­тором? Очевидно, что ответ на этот вопрос отрицателен. Построение функций с на­кап­ли­вающим параметром — приём не универсальный, и он не гарантирует получения хвос­то­вой рекурсии. С другой стороны, построение определений с накапливающим па­ра­мет­ром является делом творческим. В этом процессе необходимы некоторые эвристики.

Определение:

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

Общий вид равенств в итеративной форме может быть описан следующим образом:

f_i (p_ij) = e_ij

При этом на выражения e_ij накладываются следующие ограничения:

1. e_ij — "простое" выражение, т.е. оно не содержит рекурсивных вызовов, а только опе­ра­ции над данными.

2. e_ij имеет вид f_k (v_k), при этом v_k — последовательность простых выражений. Это и есть хвос­товая рекурсия.

3. e_ij — условное выражение с простым выражением в условии, ветви которого оп­ре­де­ля­ют­ся этими же тремя пунктами.