Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 39
Спасибо, очень интересно… Обязательно продолжайте.
И, кстати, полностью согласен с Гвидо, не вижу особой проблемы в отсутствии оптимизации хвостовой рекурсии… Python прекрасен своей умеренным сочетанием функционального и императивного подходов. Если хотите писать исключительно функционально, то существует достаточно полностью функциональных языков.
И, кстати, полностью согласен с Гвидо, не вижу особой проблемы в отсутствии оптимизации хвостовой рекурсии… Python прекрасен своей умеренным сочетанием функционального и императивного подходов. Если хотите писать исключительно функционально, то существует достаточно полностью функциональных языков.
Вот именно, что только один класс алгоритмов… И именно поэтому рекурсия никак не «базис всего программирования».
Ещё Дейкстра писал в своей работе о структурном программирование, что рекурсии достаточно для того, что бы описать любой алгоритм, а использование циклов является избыточным (слишком много лишних сущностей). Хотя стоит заметить, что в своём Алголе, он широко применял конструкции именно для циклов, но то было начало языкостроения…
Рекурсия, несомненно, божественна и прекрасна… Но тоже самое я могу сказать о циклах в Python в сравнении, например, с циклами в C++ (раз уж неделя ненависти cpp))). Ну вот не вижу я КРАЙНЕЙ необходимости в разворачивании хвостовой рекурсии… Рекурсия есть в Python, просто она всего-лишь не оптимизируется так, как это сделано в функциональных языках…
Да нормально она там применяется, питон в принципе не язык для «формулы-1», небольшие объёмы данных спокойно можно и рекурсивно обрабатывать. А там, где нужна скорость — всегда пишется расширение на C и там уж любые оптимизации доступны.
Существует несколько проектов, по «оптимизации» питона, некоторые добиваются определённых результатов, и я уверен, что при должном подходе можно его ускорить раза в 4. Но практика показывает, что это никому так уж сильно и не нужно, максимум — уменьшают влияние GIL.
Существует несколько проектов, по «оптимизации» питона, некоторые добиваются определённых результатов, и я уверен, что при должном подходе можно его ускорить раза в 4. Но практика показывает, что это никому так уж сильно и не нужно, максимум — уменьшают влияние GIL.
Зачем так критично? А как же бинарное дерево обойти иначе? Есть конечно способы обойти его без стека, но их осмысленность, как мне кажется, сомнительна.
Рекурсии достаточно чтобы описать множество алгоритмов. Описать — не значит реализовать. Может кто-то не знает, но любой рекурсивный алгоритм не очень то и сложно переписывается с использыванием явного стека (а в некоторых случаях использования явного стека позволеяет и кое-какие оптимизации производить).
*Под «явным стеком» подразумевается реализация стека в виде явной переменной в программе вместо использования стека по умолчанию.
*Под «явным стеком» подразумевается реализация стека в виде явной переменной в программе вместо использования стека по умолчанию.
Так я нигде и не писал: «долой циклы, давайте одной рекурсией пользоваться». Это было бы по меньшей мере глупо, для большинства языков.
Но в тоже время, если посмотреть на такой язык как smalltalk, то все циклические конструкции там реализованы через рекурсию, и результат на голову обходит Java. В случае с Python по мощности и удобству использования не мне судить, но то что реализация больше соответствует принципу бритвы Окама — уверен.
(говорить о рекурсии в smalltalk не совсем корректно, если не ошибаюсь использованный там приём называется fractal duck, когда объект при обработке сообщения (метода), посылает себе тоже сообщение)
Но в тоже время, если посмотреть на такой язык как smalltalk, то все циклические конструкции там реализованы через рекурсию, и результат на голову обходит Java. В случае с Python по мощности и удобству использования не мне судить, но то что реализация больше соответствует принципу бритвы Окама — уверен.
(говорить о рекурсии в smalltalk не совсем корректно, если не ошибаюсь использованный там приём называется fractal duck, когда объект при обработке сообщения (метода), посылает себе тоже сообщение)
«У любой сложной задачи есть простое и очевидное неправильное решение» (с)
Совершенно неочевидна связь между «естественно описывается» и «эффективно реализуется». Как показывает практика, зачастую это — противоположности.
Поправка: «разделяй и влавствуй» не является хвосторекурсивным по определению. Там неизбежно нужно собирать воедино результаты «покорения».
Поправка №2: рекурсия для итерации не очень нужна в отсутствии паттерн-матчинга.
Поправка №2: рекурсия для итерации не очень нужна в отсутствии паттерн-матчинга.
Читал этот ответ Гвидо давно, сейчас лень перечитывать, но такое ощущение осталось от текста, что он не понимает, что такое хвостовая рекурсия.
Хвостовая рекурсия — это не является экслюзивной фичей функциональных языков.
Не вводить TCO из-за того, что она затрудняет дебаггинг? Это бред
Не вводить TCO из-за того, Гвидо не считает рекурсию базисом в программировании? Это тоже бред
Не вводить TCO из-за того, что плохо написанный, но синтаксически корректный код может порождать баги? Это тоже бред.
Сорри, если кого обидел :)
Хвостовая рекурсия — это не является экслюзивной фичей функциональных языков.
Не вводить TCO из-за того, что она затрудняет дебаггинг? Это бред
Не вводить TCO из-за того, Гвидо не считает рекурсию базисом в программировании? Это тоже бред
Не вводить TCO из-за того, что плохо написанный, но синтаксически корректный код может порождать баги? Это тоже бред.
Сорри, если кого обидел :)
>Не вводить TCO из-за того, что плохо написанный, но синтаксически корректный код может порождать баги? Это тоже бред.
"...in the kernel we have a pretty strict «no regressions» rule, and that if
people depend on interfaces we exported having side effects that weren't
intentional, we try to fix things so that they still work unless there is a
major reason not to"
"...in the kernel we have a pretty strict «no regressions» rule, and that if
people depend on interfaces we exported having side effects that weren't
intentional, we try to fix things so that they still work unless there is a
major reason not to"
> Читал этот ответ Гвидо давно, сейчас лень перечитывать, но такое ощущение осталось от текста, что он не понимает, что такое хвостовая рекурсия.
Да, над предложенными способами реализации можно долго чесать затылок, пока не поймёшь что он «слегка» не в теме. Это подтверждается заключением «Неужели так сложно переписать вашу функцию, чтобы использовать цикл?» О косвенной рекурсии не рассказывали в школе.
Да, над предложенными способами реализации можно долго чесать затылок, пока не поймёшь что он «слегка» не в теме. Это подтверждается заключением «Неужели так сложно переписать вашу функцию, чтобы использовать цикл?» О косвенной рекурсии не рассказывали в школе.
Вообще говоря, сочетание ТСО и стектрейсов действительно совсем неочевидная задача. А без стректрейсов в эксепшнах будет грустно, плюс некоторое количество кода, пользующегося хаком в виде разбора стектрейса для доступа к рантайм значениям переменных в вызывающем коде, перестанет работать.
некоторое количество кода, пользующегося хаком в виде разбора стектрейса для доступа к рантайм значениям переменных в вызывающем коде, перестанет работать.
и поделом =) «вызывающий код» для рекурсивной функции это та же самая функция. в этом случае есть более очевидные способы передать значения переменных, нежели стектрейс. :)
Там же в комментариях попросили показать стек трейс для циклов ;)
В самой простой реализации ТСО подразумевает устранение стек трейса для _любого_ хвостового вызова. При чём тут циклы?
foo вы в стектрейсе эксепшна не увидите. вызов выглядит нормальным. как дебажить будем?
def foo(k):
k -= 2
bar(k)
def bar(i):
print 2 / i
foo(2)
foo вы в стектрейсе эксепшна не увидите. вызов выглядит нормальным. как дебажить будем?
Автор предлагает рекурсию заменить циклами, ранее выдав отмазку, что TCO ломает стек-трейсы. Есть два варианта. В первом случае Гвидо придётся показать стек-трейс для итераций цикла, во втором — доказать что *любой* алгоритм, акивно использущий стек, без потери читаемости переписывается в виде цикла (опять без стек-трейса). Ставлю месячную зар.плату, что он не сможет сделать ни того ни другого, если фанаты не начнут доказывать что «на самом деле это читаемо».
Как (хрестоматийный) пример алгоритма, активно использующего стек — лексический анализатор в виде автомата.
Как (хрестоматийный) пример алгоритма, активно использующего стек — лексический анализатор в виде автомата.
Просто Гвидо "не умеет" или не может написать "нормальную" оптимизацию (устранение) хвостовой рекурсии так, чтобы не сломать Python. А чтобы не потерять имидж, написал такую статью. Но, надо отдать должное. Парень не пытается присобачить кривой велосипед, которыми пестрят многие проекты. На этот раз....
Мне почему-то кажется, что почти все те же мысли можно повторить для того, чтоб отказатся от циклов «разварачивая» их или в просто копи-пейстнутые выражения или с использованием goto.
Я, как и многие тут, так и не понял чем же рекурсия (и хвостовая как частность) плоха?
Дебаггинг? Простите, но деббагинг сам по себе неудобен и плох. Лучше покрывать тестами. А тем кто нравится стектрейсы пусть вспомнят что сейчас все более и более популярны многопоточные алгоритмы, где важно не только стектрейс текущего вызова, а и состояние и трейсы всей системы, что делает дебаггинг еще более неудобным… так что, отказываемся от многопоточности? Те же мысли по поводу асинхронных вызовов… тоже откажемся?
А плохой код он на то и плохой, и не стоит его учитывать в принятии решения использовать что-то или нет.
Я, как и многие тут, так и не понял чем же рекурсия (и хвостовая как частность) плоха?
Дебаггинг? Простите, но деббагинг сам по себе неудобен и плох. Лучше покрывать тестами. А тем кто нравится стектрейсы пусть вспомнят что сейчас все более и более популярны многопоточные алгоритмы, где важно не только стектрейс текущего вызова, а и состояние и трейсы всей системы, что делает дебаггинг еще более неудобным… так что, отказываемся от многопоточности? Те же мысли по поводу асинхронных вызовов… тоже откажемся?
А плохой код он на то и плохой, и не стоит его учитывать в принятии решения использовать что-то или нет.
А в чём проблема была просто сделать вызов, подобный [tailcall] в Tcl 8.6, который делал бы переход на функцию?
использование всяких хаков — это всегда отстой
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Устранение Хвостовой рекурсии