Объясните мне, в чем заключается проблема оптимизации хвостового вызова и зачем она нужна Python

Question

Итак, очевидно, произошла большая суета по поводу того, нуждается ли Python в оптимизации хвостового вызова. Это пришло в голову, когда кто-то отправил Гвидо копию SICP , потому что он "не получил". Я в той же лодке, что и Гвидо. Я понимаю концепцию оптимизации хвостовых вызовов. Я просто не могу придумать причину, по которой Python действительно нуждается в этом.

Чтобы мне было легче это понять, может ли кто-нибудь дать мне фрагмент кода, который будет значительно упрощен при использовании TCO?

Answer 1

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

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

Answer 2

Если вы интенсивно хотите использовать рекурсию для вещей, которые альтернативно могут быть выражены как циклы, тогда «оптимизация хвостового вызова» действительно необходима. Однако Гвидо, Python Benevolent Dictator For Life (BDFL), твердо верит в то, что циклы выражаются в виде циклов - поэтому он не собирается использовать хвостовые вызовы особого случая (жертвуя дампами трассировки стека и регулярностью отладки).

Answer 3

Оптимизация вызовов Tail облегчает написание рекурсивных функций, не беспокоясь о переполнении стека:

def fac(n, result=1):
        if n > 1:
                return fac(n - 1, n * result)
        return result

Без оптимизации хвостового вызова, вызов этого с большим числом может переполнить стек.

Answer 4

Я размышлял над вашим вопросом в течение многих лет (хотите верьте, хотите нет ...). Я был так глубоко увлечен этим вопросом, что наконец написал целую статью (которая также представляет собой презентацию одного из моих модулей, который я написал несколько месяцев назад, не тратя времени на точное объяснение того, как это сделать). Если вы все еще заинтересованы в этом вопросе, пожалуйста, прочитайте мой ответ в моем блоге . В двух словах я представляю презентацию модуля tco ; вы не найдете ничего, что уже не можете сделать без устранения хвостовой рекурсии, но вас могут заинтересовать мои мысли об этом.

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

Answer 5

Гвидо признал в последующем посте , что TCO позволил очистить реализацию конечного автомата в виде набора функций, рекурсивно вызывающих друг друга. Однако в том же посте он предлагает альтернативное, более чистое решение без TCO.