Объясните мне, в чем заключается проблема оптимизации хвостового вызова и зачем она нужна Python
Очевидно, что возникла серьезная проблема с тем, нуждается ли Python в оптимизации хвостового вызова. Это пришло в голову, когда кто-то отправил Гвидо копию SICP, потому что он "не получил". Я в той же лодке, что и Гвидо. Я понимаю концепцию оптимизации хвостовых вызовов. Я просто не могу придумать причину, почему Python действительно нуждается в этом.
Чтобы мне было легче это понять, может ли кто-нибудь дать мне фрагмент кода, который будет значительно упрощен при использовании TCO?
5 ответов
Лично я придаю большое значение оптимизации хвостового вызова; но главным образом потому, что делает рекурсию такой же эффективной, как итерация (или делает итерацию подмножеством рекурсии). На минималистических языках вы получаете огромную выразительную силу, не жертвуя производительностью.
На "практическом" языке (таком как Python), OTOH, у вас обычно есть много других конструкций для почти каждой мыслимой ситуации, поэтому она менее критична. Всегда хорошо иметь, чтобы учесть непредвиденные ситуации, конечно
Если вы интенсивно хотите использовать рекурсию для вещей, которые могут быть альтернативно выражены как циклы, тогда "оптимизация хвостового вызова" действительно необходима. Тем не менее, Гвидо, Python Benevolent Dictator For Life (BDFL), твердо верит в то, что циклы выражаются в виде циклов - поэтому он не собирается использовать хвостовые вызовы особого случая (жертвуя дампами трассировки стека и регулярностью отладки).
Оптимизация вызовов Tail упрощает написание рекурсивных функций, не беспокоясь о переполнении стека:
def fac(n, result=1):
if n > 1:
return fac(n - 1, n * result)
return result
Без оптимизации хвостового вызова, вызов этого с большим числом может переполнить стек.
Я думал о вашем вопросе в течение многих лет (хотите верьте, хотите нет...). Я был настолько глубоко увлечен этим вопросом, что наконец написал целую статью (которая также представляет собой презентацию одного из моих модулей, который я написал несколько месяцев назад, не тратя времени на то, чтобы написать точное объяснение того, как это сделать). Если вы все еще заинтересованы в этом вопросе, пожалуйста, прочитайте мой ответ в моем блоге. В двух словах я даю презентацию модуля TCO; вы не найдете ничего, что вы уже не можете сделать без устранения хвостовой рекурсии, но вас могут заинтересовать мои мысли об этом.
Я знаю, что простые ссылки не являются предпочтительным использованием в Stackru; однако учтите, что я написал целую статью для ответа на этот пост (на которую я ссылаюсь в основной части моей статьи), включая некоторые рисунки для иллюстрации. По этой причине я размещаю здесь этот необычный ответ.
В последующем посте Гвидо признал, что TCO позволяет более четко реализовать конечный автомат как набор функций, рекурсивно вызывающих друг друга. Однако в том же посте он предлагает альтернативное, более чистое решение без TCO.