Пользователь
0,0
рейтинг
13 ноября 2012 в 01:23

Разработка → Python — оптимизация хвостовой рекурсии

Не секрет, что Python не оптимизирует хвостовую рекурсию. Более того сам Гвидо является противником этого. Но если кому нужно, есть небольшое изящное решение. Под катом…

Простое решение


class recursion(object):
    "Can call other methods inside..."
    def __init__(self, func):
        self.func = func

    def __call__(self, *args, **kwargs):
        result = self.func(*args, **kwargs)
        while callable(result): result = result()
        return result

    def call(self, *args, **kwargs):
        return lambda: self.func(*args, **kwargs)


@recursion
def sum_natural(x, result=0):
    if x == 0:
        return result
    else:
        return sum_natural.call(x - 1, result + x)

# Даже такой вызов не заканчивается исключением
# RuntimeError: maximum recursion depth exceeded
print(sum_natural(1000000))

Кстати, можно вызывать функции друг из друга в любом порядке. Код отрабатывает этот случай прекрасно:
@recursion
def sum_natural_x(x, result=0):
    if x == 0:
        return result
    else:
        return sum_natural_y.call(x - 1, result + x)

@recursion
def sum_natural_y(y, result=0):
    if y == 0:
        return result
    else:
        return sum_natural_x.call(y - 1, result + y)

print(sum_natural_x(1000000))

Вот такая получилась частица Erlang в Python )
@deko
карма
42,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (27)

  • +8
    Это называется trampoline.
    • +3
      И так реализована хвостовая рекурсия, например, в Clojure.
  • +2
    Объясните для непосвящённых в Python, как это работает.
    • +17
      Смысл в том, чтобы превратить рекурсивный вызов функции в цикл.

      Работает это так:
      1. Пишем рабочую функцию — sum_natural.
      2. Заворачиваем её в декоратор recursion.
      3. Делаем вызов sum_natural(1000000). При этом sum_natural на самом деле уже указывает не на саму функцию, а на декоратор.
      4. Вызывается метод __call__ у декоратора.
      5. В этом методе вызывается рабочая функция с переданными параметрами (1000000):
      result = self.func(*args, **kwargs)
      

      6. Функция выполняет свою логику. Если параметр x == 0, тогда просто возвращаем результат. Если же нет — значит нужно вычислять дальше. В обычной рекурсии функция просто вызвала бы саму себя с новыми параметрами. Здесь же она подготавливает и возвращает лямбду для такого вызова (обращаясь к методу call декоратора):
      return sum_natural_x.call(y - 1, result + y)
      


      7. Декоратор получает результат первого вызова. Смотрим, если результат — callable, то нам вернули лямбду для следующего вызова. Вызываем её, получаем результат, и продолжаем делать это в цикле:
      while callable(result): result = result()
      


      8. Возвращаем окончательный результат из метода __call__.
  • +1
    Кстати, будет ли это работать, если функция возвращает другую функцию?
    • +1
      Тогда надо в методе recursion.call возвращать не лямбду,
      а функцию с каким-нить кастмным свойством типа __i_am_reqursion ну и проверять его в recursion.__call__
      Но это ж некрасиво будет :)
  • +1
    Вот еще пример trampoline для рекурсии.
    Это требует модификации самой функции, так что далеко не везде применимо. Проще тогда переписать саму функцию без использования рекурсии. Для TCO в python полно хаков в виде декораторов, не требущих модификации функций.
  • –5
    Более того сам Гвидо является противником этого.
    И не напрасно — рекурсии зло (особенно в скрипт языках).
    Кстати, зато в этих языках очень просто реализовать стековые «рекурсии» на циклах, без всяких лямбд и т.д. Например, на питоне я делаю как-то так:
    def recursive_proc (a, b, c):
        stack = []
        while 1:
            ## делаем работу с текущими a, b,c :
            ...
            if next_level:
                ## push - след. уровень, текущие аргументы в стек :
                stack += [[b, c]]
                ## новые b и c
                b, c = ...
                continue;
            else:
                ## pop - возврат в пред. уровень :
                b, c = stack.pop()
                ## окончание рекурсии :
                if not len(stack):
                    break
    

    Помоему гораздо читабельнее и проще, и никаких велосипедов с трамплинами и т.д.
    • +5
      > И не напрасно — рекурсии зло (особенно в скрипт языках).

      То есть вы, как и Гвидо, не поняли, что такое хвостовая рекурсия.
      • –3
        Да нет, прекрасно понимаю, и кстати в моем примере она как раз заменена на итерацию по классике жанра. А в чем проблема?
        • 0
          1. Не понимаете, раз утверждаете, что рекурсия — зло
          2. Зачем такие извращения? Такие вещи должен делать компилятор, а не человек.
          • –1
            Очень информативно…
            А программировать за вас тоже компилятор должен? В котором месте извращение? Т.е. вы считаете что велосипед с трамплином это не извращение? Сравните код.
            И я еще раз повторяю, что прекрасно понимаю, что-такое хвостовая рекурсия. Зло в рекурсиях как раз лишний вызов и сохранение точки возврата + весь активный scope.
            Что убирается итерацией — что в примере в статье, что в моем примере, только я в моем примере сам решаю, что сохранять при следующей итерации, а что нет.

            Я просто оставлю это здесь:
            # пример из статьи:
            >>>> timeit.timeit("sum_natural(1000000)", "from __main__ import sum_natural", number = 50) / 50
            0.19649668910566448
            # мой пример:
            >>>> timeit.timeit("sum_natural_stk(1000000)", "from __main__ import sum_natural", number = 50) / 50
            0.13872319519680334
            

            И это на pypy. Как оно себя поведет без jit не проверял, но думаю что еще хуже.
            • +2
              Не пытайтесь переубедить, у dmitriid претензии не к вашему примеру, а к python вообще. Он приверженец erlang. И приблизительно этот спор уже когда-то был на хабре в какой-то теме о python ) все повторяется )
              • +1
                > у dmitriid претензии не к вашему примеру, а к python вообще.

                ваш телепатор сломался

                > И приблизительно этот спор уже когда-то был на хабре в какой-то теме о python ) все повторяется )

                ну-ну. ссылки на тот сор, я предполагаю, не появится. Если спор был похожий, то там шла речь именно о хвостовой рекурсии, а не о том, какой Питон плохой или хороший
                • 0
                  ваш телепатор сломался
                  Ок
                  ну-ну. ссылки на тот сор, я предполагаю, не появится. Если спор был похожий, то там шла речь именно о хвостовой рекурсии, а не о том, какой Питон плохой или хороший
                  Да, речь там шла о хвостовой рекурсии, но вас так эта тема задевает (неумение питоном TRE), что я сделал выводы о нелюбви к питону ) возможно, вывод неверный.
            • +2
              > А программировать за вас тоже компилятор должен?

              Нет. Мало того, из моих слов это никак не следует.

              > В котором месте извращение?

              В ручной раскрутке рекурсии, которой должен заниматься компилятор

              > Т.е. вы считаете что велосипед с трамплином это не извращение?

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

              > что прекрасно понимаю, что-такое хвостовая рекурсия. Зло в рекурсиях как раз лишний вызов и сохранение точки возврата + весь активный scope.

              То есть вы не понимаете, что такое хвостовая рекурсия. Точки возврата в хвостовой рекрусии нет

              > Что убирается итерацией — что в примере в статье, что в моем примере, только я в моем примере сам решаю, что сохранять при следующей итерации, а что нет.

              То есть вы предпочитаете выполнять тупую механическую работу, с которой прекрасно справится компилятор. Ок.
              • –2
                То есть вы не понимаете, что такое хвостовая рекурсия. Точки возврата в хвостовой рекрусии нет
                Да нет, в процедурной реализации рекурсии всегда есть точка возврата… Просто это вы не поняли: именно это критиковал van Rossum.
                В программировании когда говорится о рекурсии по умолчанию исторически подразумевается процедурная реализация оной. Независимо хвостовая она или нет. Не как в эрланге :) Потому и зло.
                То есть вы предпочитаете выполнять тупую механическую работу, с которой прекрасно справится компилятор.
                Ну где вы видите работу в двух трех строчках. Просто я предпочитаю держать рекурсию под своим контролем.

                ЗЫ. Эрланг я кстати тоже люблю и уважаю, но здесь разговор все-таки о питоне…
                • +1
                  > Да нет, в процедурной реализации рекурсии всегда есть точка возврата… Просто это вы не поняли: именно это критиковал van Rossum.

                  Нет. van Rossum говорил примерно следующее: в питоне не будет оптимизации хвостовой рекурсии потому что я не хочу и не понимаю, что это такое. Это был примерно уровень его аргументов.

                  > В программировании когда говорится о рекурсии по умолчанию исторически подразумевается процедурная реализация оной.

                  Когда говорится о хвостовой рекурсии и ее оптимизации, говорится о хвостовой рекурсии и ее оптимизации, а не о ваших фантазиях

                  Не секрет, что Python не оптимизирует хвостовую рекурсию. Более того сам Гвидо является противником этого.


                  > Ну где вы видите работу в двух трех строчках.

                  В том, что это никому не нужная механическая работа за компилятор.

                  > Эрланг я кстати тоже люблю и уважаю, но здесь разговор все-таки о питоне…

                  Осталось только понять, где я говорю про Erlang, но в глубинах чужих фантазий я не разбираюсь, увы.
                  • 0
                    Нет. van Rossum говорил примерно следующее: в питоне не будет оптимизации хвостовой рекурсии потому что я не хочу и не понимаю, что это такое.
                    Короче мы с Гвидо не понимаем что токое хвостовая рекурсия… :)
                    Хотя на самом деле мы с ним не понимаем необходимости оптимизации последней. Это такая точка зрения — можно ее разделять, можно нет.
                    Но не надо тупо, по детски, тыкать «непониманием» проблемы.
                    Мои слова "держать рекурсию под своим контролем" вы полностью проигнорировали. А в этом суть…
                    Понятливый Вы наш…
                    • 0
                      > Но не надо тупо, по детски, тыкать «непониманием» проблемы.

                      А чем еще тыкать? Если вы утверждаете — максимально безапелляционно — что «рекурсия зло», например. И предлагаете вместо того, чтобы вводить оптимизацию, заниматься тупой механической работой, которая нужна хорошо, если в 1% случаев.

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

                      > Мои слова «держать рекурсию под своим контролем» вы полностью проигнорировали. А в этом суть…

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

                      Это к вопросу о вашем «понимании».

                      Остальное я давно сказал тут: habrahabr.ru/post/111768/#comment_3568874
                      • +1
                        Нет в этом никакой сути. Наличие в языке оптимизации хвостовой рекурсии как-то отнимает у вас право писать собственный код со стеком? Нет.
                        Вот в тикле 8.6 ввели tailcall, (кстати, я как один из разрабов tcl был против) — так вот после потянулась череда правок в ядре, воркараундов и исключений, чтобы это хозяйство коректно работало с очень гибким функционалом тикля. Теперь это все крутится в namespace scope, а не в scope текущей процедуры.
                        Я к тому, что только человек со стороны, не вникая во все тонкости конструкций языка и работе ядра оного и не разбирающийся в питоне так как Гвидо, может кричать на каждом углу «дескать он не понимает» и «все это бред».
                        Вы хоть раз в исходники питона заглядывали? А надо было бы, прежде чем городить огород в приведенном выше комменте.
                        • 0
                          > Я к тому, что только человек со стороны, не вникая во все тонкости конструкций языка и работе ядра оного и не разбирающийся в питоне так как Гвидо, может кричать на каждом углу «дескать он не понимает» и «все это бред»

                          Я опираюсь на «аргументы», которые привел Гвидо. Если бы он привел хоть один аргумент, похожий на тот, что вы привели с тиклем, был бы другой разговор.

                • –2
                  ЗЫ

                  > Ну где вы видите работу в двух трех строчках. Просто я предпочитаю держать рекурсию под своим контролем.

                  Этот пример никак не доказаывает, что рекурсия зло, и что хвостовую рекурсию не нужно оптимизировать
  • +1
    Просто отлично.

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