Недавно я начал изучать Python, и я был довольно удивлен, обнаружив 1000 глубоких пределов рекурсии (по умолчанию). Если вы установите его достаточно высоким, около 30000, он выйдет из строя с ошибкой сегментации, как и C. Хотя, C, кажется, идет намного выше.

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

Я попробовал тот же эксперимент в Perl, и где-то около 10 миллионов рекурсий он потреблял все мои 4 гигабайта оперативной памяти, и я использовал ^ C, чтобы прекратить попытки. Ясно, что Perl не использует стек C, но он использует смешное количество памяти, когда повторяется - не страшно, учитывая, сколько работы ему нужно сделать для вызова функций.

Я попробовал в Пайке и был совершенно удивлен, получив 100 000 000 рекурсий за 2 секунды. Я понятия не имею, как он это сделал, но я подозреваю, что он упростил рекурсию до итеративного процесса - он, кажется, не потребляет дополнительной памяти, пока делает это. [Примечание: Пайк сглаживает тривиальные случаи, но, как мне сказали, сегрегирует ошибки в более сложных случаях.]

Я использовал эти бесполезные функции:

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) обрабатывают рекурсию и почему они так поступают. Кроме того, обратите внимание, имеет ли значение, если функция является «хвостовой рекурсивной» (см. Комментарий).