Почему Python имеет максимальную глубину рекурсии?

Question

Python имеет максимальную глубину рекурсии, но не имеет максимальной глубины итерации. Почему рекурсия ограничена? Не было бы более естественным рассматривать рекурсию как итерацию, а не ограничивать количество рекурсивных вызовов?

Позвольте мне сказать, что источник этой проблемы исходил от попытки реализовать поток (см. this question для более подробной информации о потоках). Например, предположим, что мы хотим, чтобы написать поток для производства натуральных чисел:

def stream_accum(s, n): # force the stream to a list of length n 
    def loop(s, acc): 
     if len(acc) == n: 
      return acc 
     hd, tl = s() 
     return loop(tl, acc + [hd]) 
    return loop(s, []) 


def nats(): 
    def loop(n): 
     return n, lambda: loop(n+1) 
    return loop(1) 

Рекурсивный определение потоков является весьма привлекательным. Однако, я думаю, лучший/более питонический подход будет заключаться в использовании генераторов.

Answer 1

Здесь есть несколько проблем.

Во-первых, как NPE's answer прекрасно объясняет, Python не устраняет хвостовые звонки, поэтому многие функции, которые позволят неограниченную рекурсию, скажем, в Python, ограничены.

Во-вторых, как объясняется NPE, вызовы, которые не могут быть устранены, занимают место в стеке вызовов. И даже на языках, которые делают TCE, существует множество рекурсивных функций, которые нельзя рассматривать как итерацию. (Рассмотрим наивную функцию Фибоначчи, которая рекурсивно называет себя дважды.)

Но почему стек вызовов конечный ресурс в первую очередь? Фреймы стека Python могут, по крайней мере, в принципе быть реализованы в куче и связаны друг с другом (см. Stackless для доказательства существования этого принципа), а в 64-битном пространстве памяти есть место для более чем 1000 кадров стека. (На самом деле даже C-стек практически на любой современной платформе может содержать намного больше, чем 1000 рекурсивных вызовов интерпретатора Python.)

Часть причины историческая: переводчик Python использует фиксированный стек C, чтобы называть себя рекурсивно всякий раз, когда вы делаете рекурсивный вызов, и он был первоначально разработан для 32-разрядных (и даже 24- или 20-битных) платформ, где этот C-стек довольно мал.

Но это могло быть изменено и Python 3.0 было бы идеальным местом для его изменения. Так почему же они? Потому что они приняли сознательное решение для языкового дизайна. В коде Pythonic рекурсия обычно очень мелкая (например, код os.walk, который пересекает мелкие древовидные структуры); если ваша функция достигает глубины около 1000, это скорее будет ошибкой, чем быть преднамеренной. Таким образом, предел остается. Конечно, это немного круговое - если они удалили предел (и, особенно, если они устранили хвостовые звонки), более глубокая рекурсия стала бы более идиоматичной. Но это своего рода точка - Гвидо не хочет языка, где глубокая рекурсия идиоматична. (И большая часть сообщества Python согласна.)

Answer 2

Рекурсия требует места на call stack, который имеет ограниченный размер. Код, который использовал слишком много уровней рекурсии, даст ошибку, названную stack overflow (также прославленный some obscure website). Кажется, что Python ограничивает это (бит произвольно) до 1000 уровней или около того, но это can be increased, установив sys.setrecursionlimit.

Итерация использует что-то вроде for -loop, который реализуется путем увеличения некоторого счетчика и условной установки instruction pointer обратно в начало цикла. Это постоянное значение в памяти.

Answer 3

Это не уникально для Python и имеет отношение к каждому вызову, занимающему место на call stack, и размер стека ограничен.

Итерация сама по себе не использует пространство стека и поэтому не подпадает под это ограничение.

Не каждый рекурсивный вызов требует использования пространства стека. Например, некоторые языки могут автоматически преобразовывать tail recursion в итерацию. Однако CPython не делает этого (Does Python optimize tail recursion?).

Вы можете увеличить максимальную глубину стека вызовов Python, вызвав sys.setrecursionlimit.