Выполняет ли MATLAB оптимизацию хвостового вызова?

Недавно я узнал Haskell, и, когда это возможно, я стараюсь нести чистый функциональный стиль в свой другой код. Важным аспектом этого является рассмотрение всех переменных как неизменяемых, т.е. Констант. Для этого многие вычисления, которые будут реализованы с использованием циклов в императивном стиле, должны выполняться с использованием рекурсии, что обычно приводит к штрафу памяти из-за выделения нового стека кадров для каждого вызова функции. В специальном случае хвостового вызова (где возвращаемое значение вызываемой функции сразу возвращается вызывающему абоненту), однако это наказание можно обойти процессом, называемым оптимизацией хвостовых вызовов (одним способом это можно сделать существенно заменив вызов с помощью jmp после правильной настройки стека). MATLAB выполняет TCO по умолчанию, или есть способ рассказать об этом?

Ответы

Ответ 1

Если я определяю простую хвосто-рекурсивную функцию:

function tailtest(n)
  if n==0; feature memstats; return; end
  tailtest(n-1);
end

и назовите его так, чтобы он довольно глубоко заработал:

set(0,'RecursionLimit',10000);
tailtest(1000);

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

set(0,'RecursionLimit',10000);
tailtest(5000);

тогда (на моей машине, сегодня) MATLAB просто падает: процесс бесцеремонно умирает.

Я не думаю, что это соответствует MATLAB, выполняющему любую TCO; случай, когда функция tail-вызывает себя, только в одном месте, без локальных переменных, отличных от одного аргумента, почти так же проста, как можно было бы надеяться.

Итак: Нет, похоже, что MATLAB вообще не делает TCO, по крайней мере по умолчанию. Я пока не искал варианты, которые могли бы его включить. Я был бы удивлен, если бы они были.

В случаях, когда мы не взорвали стек, сколько стоит рекурсия? См. Мой комментарий к Биллу Чейтхаму: ответьте, что время накладное, нетривиальное, но не безумное.

... За исключением того, что Билл Чиатам удалил свой ответ после того, как я оставил этот комментарий. ОК. Итак, я взял простую итеративную реализацию функции Фибоначчи и простой хвосто-рекурсивный, выполнив по существу одно и то же вычисление в обоих, и приурочил их как к fib(60). Рекурсивная реализация потребовала в 2,5 раза дольше, чем итеративная. Конечно, относительные служебные данные будут меньше для функций, которые выполняют больше работы, чем одно сложение и одно вычитание на итерацию.

(Я также согласен с настроем delnan: очень рекурсивный код такого рода, который чувствует себя естественно в Haskell, как правило, может быть унииоматичным в MATLAB.)