Обнаружение Бесконечной рекурсии в Python или динамических языках
Недавно я попытался компилировать, программируют что-то вроде этого с GCC:
int f(int i){
if(i<0){ return 0;}
return f(i-1);
f(100000);
и это работало очень хорошо. Когда я осмотрел стековые фреймы, компилятор оптимизировал программу для использования только одного кадра, просто перейдя назад к началу функции и только замены аргументов f. И - компилятор даже не работал в оптимизированном режиме.
Теперь, когда я пробую то же самое в Python - я врезался в максимальную стену рекурсии (или вероятно переполнение стека, если я установил глубину рекурсии слишком высоко).
Есть ли способ, которым динамический язык как Python может использовать в своих интересах эту хорошую оптимизацию? Возможно, возможно использовать компилятор вместо интерпретатора для создания этой работы?
Просто любопытный!
3 ответа
Оптимизация, о которой вы говорите, известна как устранение хвостового вызова - рекурсивный вызов разворачивается в итеративный цикл.
Было некоторое обсуждение этого, но текущая ситуация такова, что это не будет добавлено, по крайней мере, в сам cpython. См. запись в блоге Гвидо для некоторого обсуждения.
Однако существуют некоторые декораторы, которые манипулируют функцией для выполнения этой оптимизации. Обычно они позволяют сэкономить только место, но не время (на самом деле, они обычно работают медленнее)
.Это не имеет ничего общего с тем, что это динамический язык или что он интерпретируется. CPython просто не реализует оптимизацию Tail Recursion . Вы можете обнаружить, что это делают JPython и т. Д.
Когда я проверил кадры стека, компилятор оптимизировал программу для использования только одного кадра, просто вернувшись к началу функции и заменив только аргументы f.
То, что вы описываете, называется "хвостовой рекурсией". Некоторые компиляторы/интерпретаторы поддерживают ее, некоторые нет. На самом деле, большинство не поддерживают. Как вы заметили, gcc поддерживает. И на самом деле, хвостовая рекурсия является частью спецификации языка программирования Scheme, поэтому все компиляторы/интерпретаторы Scheme должны поддерживать хвостовую рекурсию. С другой стороны, компиляторы таких языков, как Java и Python (а также большинства других языков, я бы сказал), не поддерживают хвостовую рекурсию.
Может ли такой динамический язык, как Python, воспользоваться этими хорошими оптимизациями?
Вы имеете в виду, прямо сейчас, или вы спрашиваете в более абстрактных терминах? Если говорить абстрактно, то да! Было бы абсолютно возможно, чтобы динамические языки использовали преимущества хвостовой рекурсии (Scheme, например, использует). Но если говорить конкретно, то нет, CPython (канонический интерпретатор Python) не имеет флага или другого параметра для включения хвостовой рекурсии.