Как Python обрабатывает бесконечную рекурсию?

Поэтому, играя с Python, я заметил, что в основном нет ограничений на размер стека программы (продолжал выполнять операции с питанием для числа, точность оставалась идеальной даже после того, как дошли до тысяч цифр). Это заставляет меня задуматься: а что, если я случайно попаду в бесконечный рекурсивный цикл в Python? Компилятор заметит и выдаст ошибку переполнения стека? Или программа просто вылетит? Сгорел бы мой процессор? Честно говоря, мне не хотелось бы это проверять.


python recursion infinite
person Coffee Maker    schedule 22.07.2014    source источник
comment
возможный дубликат рекурсии Python max, вопрос о sys.setrecursionlimit ()   -  person Cory Kramer    schedule 23.07.2014
comment
Python имеет ограничение рекурсии, которое можно установить с помощью sys.setrecursionlimit: docs. python.org/2/library/sys.html#sys.setrecursionlimit   -  person mgilson    schedule 23.07.2014
comment
Значит, на рекурсию нет ограничений? (по умолчанию)   -  person Coffee Maker    schedule 23.07.2014
comment
Объекты Python размещаются в куче. Тот факт, что вы можете создавать очень большие целые числа, ничего не говорит вам о размере стека, потому что объем используемой памяти стека не зависит от размера объекта.   -  person Weeble    schedule 23.07.2014

Ответы (2)


arrow_upward
7
arrow_downward

Я обещаю, что ни один современный компьютер не сгорит из-за пользовательского кода. Попробуйте сами:

def recurseInfinitely( n ):
    recurseInfinitely(n+1)

recurseInfinitely(0)

Быстрый запуск этой программы дает результат:

  [...]
    recurseInfinitely(n+1)
  File "so.py", line 2, in recurseInfinitely
    recurseInfinitely(n+1)
  File "so.py", line 2, in recurseInfinitely
    recurseInfinitely(n+1)
RuntimeError: maximum recursion depth exceeded

Вы можете поймать ошибку и проверить значение n:

def recurseInfinitely( n ):   
    try:
        recurseInfinitely(n+1)
    except RuntimeError:
        print "We got to level %s before hitting the recursion limit."%n

И получить:

Мы добрались до 997-го уровня до того, как достигли лимита рекурсии.

person Russell Borogove    schedule 23.07.2014

arrow_upward
3
arrow_downward

Python (по крайней мере, эталонная реализация) этого не делает - у вас не может быть бесконечного рекурсивного цикла, как в некоторых функциональных языках. Он вызовет исключение, когда рекурсия достигнет глубины около 1000 (по умолчанию это можно изменить с помощью sys.setrecursionlimit). Так что да, программа вылетит.

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

Пользователь larsmans прокомментировал, что встроенный предел глубины рекурсии достаточно хорош для большинства практических алгоритмов, но итеративная форма обычно работает лучше - причина в том, что вызовы функций в Python обходятся дорого.

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

person Paulo Scardine    schedule 22.07.2014
comment
Во многих практических рекурсивных алгоритмах глубина рекурсии логарифмична от размера входных данных (подумайте о сортировке, стабильных суммах). Таким образом, с настройками по умолчанию алгоритмы верны максимум для 2 ** (1000-c) элементов для c небольшой константы. Для меня этого достаточно. - person Fred Foo; 23.07.2014
comment
Однако, если вы создаете библиотеку, которая, как ожидается, будет обрабатывать большие объемы данных, очевидно, что итерация лучше. У меня были проблемы с библиотекой биоинформатики, когда она была реализована рекурсивно. ›_‹ - person xdhmoore; 23.01.2017