Линейные рекурсия и итерация. Чего не хватает Python

Рассмотрим эти 2 процесса на примере(рассмотренного мной ранее) вычисления факториала. Мы можем вычислить n!, вычислив сначала (n − 1)!, а затем умножив его на n. После того, как мы добавляем условие, что 1! равен 1, это наблюдение можно непосредственно перевести в процедуру. В рекурсивной реализации это выглядит следующим образом.

*-Нравится статья? Кликни по рекламе! :)

Теперь рассмотрим вычисление факториала с другой точки зрения. Мы можем описать правило вычисления n!, сказав, что мы сначала умножаем 1 на 2, затем результат умножаем на 3, затем на 4, и так пока не достигнем n. Мы можем описать это вычисление, сказав, что счетчик и произведение с каждым шагом одновременно изменяются согласно правилу:

произведение = счетчик · произведение
счетчик = счетчик + 1

и добавив условие, что n! — это значение произведения в тот момент, когда счетчик становится больше, чем n.

def factorial(n):
    def factIter(product, counter):
        if counter>n:
            return product
        else:
            return factIter(counter*product, counter+1);
    return factIter(1, 1)

 Сравним эти два процесса. С одной стороны, они кажутся почти одинаковыми. Оба они вычисляют одну и ту же математическую функцию с одной и той же областью определения, и каждый из них для вычисления n! требует количества шагов, пропорционального n. Действительно, два этих процесса даже производят одну и ту же последовательность умножений и получают одну и ту же последовательность частичных произведений. С другой стороны, когда мы рассмотрим «формы» этих двух процессов,
мы увидим, что они ведут себя совершенно по-разному Возьмем первый процесс. Расширение происходит по мере того, как процесс строит цепочку отложенных операций (deferred operations), в данном случае цепочку умножений. Сжатие происходит тогда, когда выполняются эти отложенные операции. Такой тип процесса, который характеризуется цепочкой отложенных операций, называется рекурсивным процессом (recursive process). Выполнение этого процесса требует, чтобы интерпретатор запоминал, какие операции ему нужно выполнить впоследствии. При вычислении n! длина цепочки отложенных умножений, а следовательно, и объем информации, который требуется, чтобы ее сохранить, растет линейно с ростом n (пропорционален n), как и число шагов. Такой процесс называется линейно рекурсивным процессом (linear recursive process).
Напротив, второй процесс не растет и не сжимается. На каждом шаге при любом значении n необходимо помнить лишь текущие значения переменных product, counter и max-count. Такой процесс мы называем итеративным (iterative process).
В общем случае, итеративный процесс — это такой процесс, состояние которого можно описать конечным числом переменных состояния (state variables) плюс заранее заданное правило, определяющее, как эти переменные состояния изменяются от шага к шагу, и плюс (возможно) тест на завершение, который определяет условия, при которых процесс должен закончить работу. При вычислении n! число шагов линейно растет с
ростом n. Такой процесс называется линейно итеративным процессом (linear iterative process).
Противопоставляя итерацию и рекурсию, нужно вести себя осторожно и не смешивать понятие рекурсивного процесса с понятием рекурсивной процедуры. Когда мы говорим, что процедура рекурсивна, мы имеем в виду факт синтаксиса: определение процедуры ссылается (прямо или косвенно) на саму эту процедуру. Когда же мы говорим о процессе, что он следует, скажем, линейно рекурсивной схеме, мы говорим о развитии процесса, а не о синтаксисе, с помощью которого написана процедура.
Различие между процессами и процедурами может запутывать отчасти потому, что большинство реализаций обычных языков (включая Аду, Паскаль и Си) построены так, что интерпретация любой рекурсивной процедуры поглощает объем памяти, линейно растущий пропорционально количеству вызовов процедуры, даже если описываемый ею процесс в принципе итеративен. Как следствие, эти языки способны описывать итеративные процессы только с помощью специальных«циклических конструкций» вроде: do, repeat, until, for и while(увы, к таким относится и Python).
Но бывают языки, в которых, итеративный процесс будет выполнять используя фиксированный объем памяти, даже если он описывается рекурсивной процедурой(к таковым, например, относится Lisp). Такое свойство реализации языка называется поддержкой хвостовой рекурсии (tail recursion). Если реализация языка поддерживает хвостовую рекурсию, то итерацию можно выразить с помощью обыкновенного механизма вызова функций, так что специальные циклические конструкции имеют смысл только как синтаксический сахар.
P.S. в Питоне нет оптимизации хвостовой рекурсии (а недавно Гвидо подтвердил, что и не будет), что делает практически невозможным программирование в характерном для ФП рекурсивном стиле.
UPD. Написал пример использования рекурсивного подхода(или даже более глобально - мышления). Динамическое программирование: размен денег.
Используемая литература:

1. http://mitpress.mit.edu/sicp/