Обнаружение бесконечной рекурсии в Python или динамических языках

Question

Недавно я пытался скомпилировать программу с помощью GCC:

int f(int i){
    if(i<0){ return 0;}
    return f(i-1);
f(100000);

и все прошло нормально. Когда я проверял кадры стека, компилятор оптимизировал программу, чтобы использовать только один кадр, просто вернувшись назад к началу функции и заменив аргументы на f. И - компилятор даже не работал в оптимизированном режиме.

Теперь, когда я пытаюсь сделать то же самое в Python - я достигаю максимальной стены рекурсии (или, возможно, переполнения стека, если я установил слишком большую глубину рекурсии).

Есть ли способ, которым динамический язык, такой как python, может воспользоваться этими приятными оптимизациями? Может быть, можно использовать компилятор вместо интерпретатора, чтобы сделать эту работу?

Просто любопытно!

Answer 1

Оптимизация, о которой вы говорите, известна как устранение хвостового вызова - рекурсивный вызов разворачивается в итеративный цикл.

Об этом уже шла речь, но в настоящее время ситуация такова, что это не будет добавлено, по крайней мере, в собственно cpython. См. запись в блоге Гвидо для обсуждения.

Однако существуют некоторые декораторы , которые управляют функцией для выполнения этой оптимизации. Обычно они получают только экономию места, но не время (на самом деле они обычно медленнее)

Answer 2

Когда я проверял кадры стека, компилятор оптимизировал программу для использования только одного кадра, просто вернувшись назад в начало функции и заменив аргументы только на f.

То, что вы описываете, называется "хвостовой рекурсией". Некоторые компиляторы / интерпретаторы поддерживают это, некоторые нет. На самом деле большинство этого не делают. Как вы заметили, gcc делает. Фактически, хвостовая рекурсия является частью спецификации языка программирования Scheme, поэтому все компиляторы / интерпретаторы Scheme должны поддерживать хвостовую рекурсию. С другой стороны, компиляторы для таких языков, как Java и Python (а также для большинства других языков, на которые я бы поставил), не выполняют хвостовую рекурсию.

Есть ли способ, которым динамический язык, такой как python, может воспользоваться этими приятными оптимизациями?

Вы имеете в виду прямо сейчас , или вы спрашиваете в более абстрактных терминах? Говоря абстрактно, да! Для динамических языков было бы абсолютно возможно использовать преимущества хвостовой рекурсии (например, Scheme). Но если говорить конкретно, то нет, CPython (канонический интерпретатор Python) не имеет флага или другого параметра для включения хвостовой рекурсии.

Answer 3

Это не имеет ничего общего с тем, что это динамический язык или что он интерпретируется. CPython просто не реализует Хвостовая рекурсия оптимизация. Вы можете обнаружить, что JPython и т. Д. Делают.