Как Ваш любимый язык обрабатывает глубокую рекурсию? [закрытый]

Это - больше вопроса о реализации, чем вопрос о языке. Нет ничего останавливающего некоторого (stoopid) конструктора компилятора C от также ограничения их стека вызовов к 1 000. Существует много маленьких процессоров там, которые не имели бы стекового пространства для даже что многие.

(Люди Python быстры, чтобы указать, что можно всегда преобразовывать рекурсивные функции в повторяющиеся и что они всегда быстрее. Это на 100% верно. Это не действительно, о чем мой вопрос все же.)

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

может иметь место, что повторяющееся решение / решение для стека всегда быстрее в Python . Если так, это - сбой Python, не рекурсии.

PHP имеет предел по умолчанию 100, прежде чем он умрет:

Fatal error: Maximum function nesting level of '100' reached, aborting!

Редактирование: можно изменить предел с ini_set('xdebug.max_nesting_level', 100000);, но если Вы выходите за предел приблизительно 1 150 повторений катастрофические отказы PHP:

[Fri Oct 24 11:39:41 2008] [notice] Parent: child process exited with status 3221225477 -- Restarting.

C#/.NET будет использовать хвостовую рекурсию в определенном наборе обстоятельств. (Компилятор C# не испускает tailcall код операции, но , JIT реализует хвостовую рекурсию в некоторых случаях .

у Шри Borde также есть сообщение по этой теме . Конечно, CLR постоянно изменяется, и с.NET 3.5, и 3.5SP1 это, возможно, изменилось снова относительно последних вызовов.

Используя следующее в интерактивной консоли F#, это работало в меньше, чем секунда:

let rec f i l = 
  match i with 
  | i when i < l -> f (i+1) l
  | _ -> l

f 0 100000000;;

я тогда попробовал прямой перевод т.е.

let rec g i l = if i < l then g (i+1) l else l

g 0 100000000;;

Тот же результат, но различная компиляция.

Это - то, в чем похож f, когда переведено в C#:

int f(int i, int l)
{
  while(true)
  {
    int num = i;
    if(num >= l)
      return l;
    int i = num;
    l = l;
    i = i + 1;
  }
}

g, однако переводится в это:

int g(int i, int l)
{
  while(i < l)
  {
    l = l;
    i++;
  }
  return l;
}

интересно, что две функции, которые являются существенно тем же, представляются по-другому компилятором F#. Это также показывает, что компилятор F# имеет рекурсивную хвостом оптимизацию. Таким образом это должно циклично выполниться, пока я не достигаю предела для 32-разрядных целых чисел.

Согласно этому потоку, приблизительно 5 000 000 с Java, RAM на 1 ГБ. (и что, с 'клиентской' версией горячей точки)

, Который был с стек (-Xss) из 300 мес.

С - параметр сервера , который мог быть увеличен.

Также можно попытаться оптимизировать компилятор ( со СТРУЕЙ , например) для сокращения стека наверху на каждом слое.

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

Протестированный с:

function f(i, l)
    if i < l then
        return f(i+1, l)
    end
    return i
end

local val1  = arg[1] or 1
local val2  = arg[2] or 100000000
print(f(val1 + 0, val2 + 0))

Также с:

function g(i, l)
    if i >= l then
        return i
    end
    return g(i+1, l)
end

и даже попробованная перекрестная рекурсия (f звонящий g и g, звонящий f...).

В Windows, Lua 5.1 использует приблизительно 1.1 МБ (постоянные) для выполнения этого, концов за несколько секунд.

Визуальный Dataflex будет переполнение стека.

Я - настоящий поклонник функционального программирования, и так как большинство тех языков реализует оптимизацию последнего вызова, можно рекурсивно вызвать столько, сколько Вам нравится:-P

Однако практически, я должен использовать много Java и использовать Python много также. Никакая идея, что предельный Java имеет, но для Python, который я на самом деле запланировал (но еще не сделали его) реализовать декоратора, который был бы последний вызов оптимизировать украшенную функцию. Я планировал это для не оптимизации рекурсии, но главным образом как упражнение в динамичном исправлении байт-кода Python и получении дополнительной информации о внутренностях Python. Вот некоторые интересные ссылки: http://lambda-the-ultimate.org/node/1331 и http://www.rowehl.com/blog/?p=626

Существует способ улучшить Perl код, чтобы заставить его использовать постоянную стопку размера. Вы делаете это при помощи специальной формы goto.

sub f{
  if( $_[0] < $_[1] ){

    # return f( $_[0]+1, $_[1] );

    @_ = ( $_[0]+1, $_[1] );
    goto &f;

  } else {
    return $_[0]
  }
}

Когда сначала названный им выделит место на стеке. Затем это изменит свои аргументы и перезапустит подпрограмму, не добавляя ничего больше к стеку. Это поэтому притворится, что никогда не называло сам, изменяя его в итеративный процесс.

Вы могли также использовать Sub:: Звоните:: Повторитесь модуль. Который делает код легче понять, и короче.

use Sub::Call::Recur;
sub f{
  recur( $_[0]+1, $_[1] ) if $_[0] < $_[1];
  return $_[0];
}