Недавно я начал изучать Python, и я был довольно удивлен, обнаружив предел 1000 глубоких рекурсий (по умолчанию). Если вы установите его достаточно высоким, около 30000, он выйдет из строя с ошибкой сегментации, как и C. Хотя, похоже, C выглядит намного выше.
(Люди из Python быстро указывают, что вы всегда можете преобразовывать рекурсивные функции в итеративные и что они всегда быстрее. Это 100% истинно. На самом деле это не совсем мой вопрос.)
Я пробовал тот же эксперимент в Perl и где-то около 10 миллионов рекурсий он потреблял все мои 4 гигабайта, и я использовал ^ C, чтобы перестать пытаться. Ясно, что Perl не использует стек C, но он использует смехотворный объем памяти, когда он рекурсирует - не ужасно шокирует, учитывая, сколько работы он должен выполнять для вызова функций.
Я попытался в Пайке и был полностью удивлен, получив 100 000 000 рекурсий примерно через 2 секунды. Я понятия не имею, как это произошло, но я подозреваю, что он сплющил рекурсию на итеративный процесс - он, похоже, не потребляет лишней памяти, пока он это делает. [Примечание: Пайк сглаживает тривиальные случаи, но segfaults на более сложных, или так мне говорят.]
Я использовал эти бесполезные функции:
int f(int i, int l) { if(i<l) return f(i+1,l); return i; }
sub f { return f($_[0]+1, $_[1]) if $_[0]<$_[1]; return $_[0] };
def f(i,l):
if i<l:
return f(i+1,l)
return i
Мне очень любопытно, как другие языки (например, PHP, Ruby, Java, Lua, Ocaml, Haskell) обрабатывают рекурсию и почему они так ее обрабатывают. Кроме того, обратите внимание, не имеет значения, является ли функция "хвостовой рекурсивной" (см. Комментарий).
