Оптимизация хвостовой рекурсии в питоне

Почему вдруг ее нет? Не могут сделать?

Можно попробовать реализовать самому: заменить рекурсию на цикл с сохранением промежуточных значений в списках. И посмотреть, что получится.

Потому что питон - это крайне перегруженный различными хаками язык, из-за чего интерпретатор не может знать, вызываешь ли ты функцию, конструктор объекта, написанный на Си обработчик операции-вызова, или еще черт пойми что. По этой причине все проекты оптимизации на этапе компиляции провалились, и живы остались только JIT оптимизаторы, которые конкретный фактически маршрут выполнения пытаются сократить для повторного прохода.

Не могут сделать?

Именно так.

Правильно я понимаю, что абсолютно любая функция с рекурсией большой глубины приведет к ошибке переполнения стека?

Да.

https://stackoverflow.com/questions/27417874/tail-recursion-optimization-deco...

Всё уже сделано до нас.

А взаимную рекурсию оно умеет? Плюс, оно на каждый шаг цикла кидает эксепшон. Это просто офигенная оптимизация, я тебе скажу.

интерпретатор не может знать, вызываешь ли ты функцию, конструктор объекта, написанный на Си обработчик операции-вызова, или еще черт пойми что

А как же он работает, когда фунуцию от объекта отличить не может? Это фигня полная.

А какие практические задачи обычно решают с помощью хвостовой рекурсии?

Решают при помощи рекурсии. А речь идет об оптимизации рекурсии интепретатором питона таким образом, что можно работать с бесконечной рекурсией без переполнения стека.

А какие практические задачи обычно решают с помощью хвостовой рекурсии?

Решают при помощи рекурсии.

Блестящий ответ.

Использование рекурсии очень сильно упрощает программу, если речь идет об объектах, которые сами определяются рекурсивно. Например списки или фрактальтные объекты.

Это первая попавшаяся ссылка. Скорее в шутку. «Оптимизация» и «Python» в одном предложении — это всегда юмор.

Нужно пребывать в терминальной стадии ФП головного мозга, чтобы определять список посредством рекурсии.

Что касается вещей вроде фракталов, деревьев, графов, то одной только *хвостовой* рекурсии не достаточно, чтобы реализовать весь набор интересных операций с ними. И, стало быть, оптимизация хвостовой рекурсии значительной выгоды для этих задач не даст..

«Оптимизация» и «Python» в одном предложении — это всегда юмор.

+1

не угадали.

Because nested structures appear in almost every problem domain and programming environment, from databases to 3D graphics to filesystems, the act of iterating through these structures is common, so common that most programmers barely notice when they’re doing it. As such, generalizing the act of recursive traversals provides immediate real-world benefits: our new generalized traversal can replace a host of type-specific traversal functions. In addition, by decoupling how a function recurses over data from what the function actually does, we reduce cognitive overhead and can focus entirely on the core behavior of our recursive functions. No matter the structures in question—lists, directory hierarchies, control flow graphs, database records—recursion schemes bring us an orderly and predictable way to traverse them.

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

В питоне абсолютно любая функция с рекурсией большой глубины приведет к ошибке переполнения стека. Значит питон для задач указанных выше не подходит вообще.

абсолютно любая функция с рекурсией большой глубины приведет к ошибке переполнения стека?

А где-то это не так?

+100

Мне от питона каждый раз рыдать хочется после нормальных языков.

Где язык умеет оптимизировать хвост. рекурсию. Хаскель, Скала, лисп.

Питон сам по себе в ~10 раз тормознее си-шки. Питон не умеет в многопоточность. С такими вводными, произносить слово «оптимизация» и одновременно сохранять серьезное выражение лица - невозможно.

Или ты под словом «оптимизация» подразумеваешь переписывание откровенного говнокода?

+ Эрланг, Эликсир.

<портянка на латиннице>

Вообще, для работы с большими контейнерами (бд, фс, и так далее) общепринято использовать курсоры (итераторы, указатели), а не рекурсию.

В питоне абсолютно любая функция с рекурсией большой глубины приведет к ошибке переполнения стека.

Если бы хвостовая рекурсия к переполнению не приводила, качественной разницы это не сделало бы.

Значит питон для задач указанных выше не подходит вообще.

Как быть со всеми теми, кто на питоне работает со списками, бд, фс и графами, и никаких трудностей не испытывает?

Вопрос так и остался почему не сделают? При такой популярности и широком использовании питона? Есть что-то принципиальное типа «глобальной блокировки интепретатора»?

Вопрос так и остался почему не сделают?

Не ясно, ради чего это делать.

Откуда в питоне указатели? Там же автоматическое управление памятью.

Напиши в питоне рекурсивную функцию n!(123456) тогда поймешь.

Не ясно, ради чего это делать.

Ради того, что многие алгоритмы гораздо легче записываются в рекурсивной форме чем в итеративной.

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

Ради того, что многие алгоритмы гораздо легче записываются в рекурсивной форме чем в итеративной.

Да, именно так, но в случае хвостовой рекурсией есть ограничение в виде отсутствия возможности определить логику сразу после рекурсивного вызова, с таким ограничением многие алгоритмы резко теряют в понятности и проигрывают итеративным алгоритмам.

Это можно обойти путём передачи коллбэка. Но да, без всяких плюшек со стороны языка будет выглядеть всрато.

Вопрос так и остался почему не сделают?

Не ясно, ради чего это делать.

Напиши в питоне рекурсивную функцию n!(123456) тогда поймешь.

Не ясно, ради чего писать функцию, которая отлично пишется циклом, рекурсивно.

Не ясно, ради чего писать функцию, которая отлично пишется циклом, рекурсивно.

Вот и я о том же: Оптимизация хвостовой рекурсии в питоне (комментарий)

А как же он работает, когда фунуцию от объекта отличить не может? Это фигня полная.

По месту разбирается. И так - каждую операцию.

Вот и я о том же

Можно попробовать реализовать самому: заменить рекурсию на цикл с сохранением промежуточных значений в списках. И посмотреть, что получится.

Ну ты прав.

Рекурсия — это повторный вызов функции. При вызове функции локальные переменные неявно сохраняются на стеке вызовов. При повторных вызовах стек вызовов соответственно растёт.

Ничто не мешает сделать явный стек (в питоне обычно используют класс list) и сохранять туда значения явно.

В питоне абсолютно любая функция с рекурсией большой глубины приведет к ошибке переполнения стека.

Жавайте уточнять, что речь идет про CPython. Не все реализации питона страдают этой проблемой.

math.factorial(x)

Не?

Прикол с хвостовой рекурсией в том, что стек вообще не нужен, необходимо сохранять только последний результат.

Напиши рекурсивную функцию n!(123456) тогда поймешь.

1. А то же самое написать через итерацию - не судьба?
2. Мсье не в курсе, что цивилизованные люди факториалы таким способом не считают? Идите просвещайтесь - https://gmplib.org/manual/Factorial-Algorithm.html

Напиши в питоне функцию n!(123456) тогда поймешь.

Извольте:

from math import factorial
factorial(123456)

многие алгоритмы гораздо легче записываются в рекурсивной форме чем в итеративной

Речь про *хвостовую* рекурсию, а не про рекурсию как таковую.

Почему вдруг ее нет? Не могут сделать?

А зачем она нужна?

в ~10 раз тормознее сишки

оптимистично. в реальности там скорее 10^6 или 10^7 раз. быстрый «python» это когда вся программа написана на c++ и обвязана питоном сверху.

там скорее 10**6 или 10**7 раз

пофиксил, не благодари

Дебилушка, не позорься. Не умеешь фп так закрой калитку.

Этот мсье на самом деле мадам (мамзель?)

Думаю, в данном случае не важно, что там у мсье в штанах.

Как показывает опыт, содержимое штанов часто коррелирует с содержимым черепной коробки.

Because

Ой какой умный — английский знает. А погуглить вопрос по-английски не пробовал? Ответ буквально на первой же странице: хорошие бектрейсы сочли более важными.

Потому что рекурсия становится тем неудобнее, чем больше состояния нужно передавать между отдельными «итерациями».

Хвостовая рекурсия, это вообще не самая приятная вещь. Скажем, если реализовать простейший фильтр по предикату «в лоб» типа

(defun filter (list predicate)
    (and list
        (if (funcall predicate (car list))
            (cons (car list) (filter (cdr list) predicate))
            (filter (cdr list) predicate))))

В общем, если ты только что впервые в жизни посчитал факториал или числа фибоначчи рекурсивно и тебе кажется, что ты познал мир, это не так. Рекурсия далеко не всегда проще — попробуй рекурсивно реализовать while + break и доложи об ощущениях.

Ответ буквально на первой же странице: хорошие бектрейсы сочли более важными.

Не только бектрейсы. BDFL упоминал также сомнительность TCO как оптимизации и незанчительный вклад рекурсий в создание программ на питоне. А потом уже он ставит проблему «хз, как эту оптимизацию вообще возможно будет сделать с нынешним интерпретатором».

У меня был кусок кода, который выглядел, как Y-комбинатор и использовал внизу исключения с трамплином. А может и декоратор был. Не помню. Раскручивались исключения невероятно медленно, поэтому мысль о том, чтобы писать рекурсивные лупы, я бросил.

Не могут

Не хотят. Суть питона не в том, чтобы дать тебе гибкий и годный инструмент, а в том, чтобы налабать и готово. Шаг влево, шаг вправо — не питонично.

А всего-то можно было понаписать с полтонны ffi для какого-нибудь из лиспов, учитывая то, что FFI-обвязки для какого-нибудь Guile пишутся невероятно проще.

Нужно пребывать в терминальной стадии ФП головного мозга, чтобы определять список посредством рекурсии.

Что не так? Списки так и определяются. Либо у нас пустой список, либо пара голова::хвост списка.