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

Void

Дата 5.3.2006, 23:47 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 10
Всего: 173

Случайно натолкнулся (по ссылке с этого поста в ЖЖ) на код, позволяющий организовать в Питоне сворачивание хвостовой рекурсии в цикл, типичное для функциональных языков, с помощью декораторов и манипуляций со стеком. На мой взгляд, очень интересная демонстрация возможностей Питона.
Код взят из ASPN Python Cookbook.

Код


#!/usr/bin/env python2.4
# This program shows off a python decorator(
# which implements tail call optimization. It
# does this by throwing an exception if it is 
# it's own grandparent, and catching such 
# exceptions to recall the stack.

import sys

class TailRecurseException:
  def __init__(self, args, kwargs):
    self.args = args
    self.kwargs = kwargs

def tail_call_optimized(g):
  """
  This function decorates a function with tail call
  optimization. It does this by throwing an exception
  if it is it's own grandparent, and catching such
  exceptions to fake the tail call optimization.
  
  This function fails if the decorated
  function recurses in a non-tail context.
  """
  def func(*args, **kwargs):
    f = sys._getframe()
    if f.f_back and f.f_back.f_back \
        and f.f_back.f_back.f_code == f.f_code:
      raise TailRecurseException(args, kwargs)
    else:
      while 1:
        try:
          return g(*args, **kwargs)
        except TailRecurseException, e:
          args = e.args
          kwargs = e.kwargs
  func.__doc__ = g.__doc__
  return func

@tail_call_optimized
def factorial(n, acc=1):
  "calculate a factorial"
  if n == 0:
    return acc
  return factorial(n-1, n*acc)

print factorial(10000)
# prints a big, big number,
# but doesn't hit the recursion limit.

@tail_call_optimized
def fib(i, current = 0, next = 1):
  if i == 0:
    return current
  else:
    return fib(i - 1, next, current + next)

print fib(10000)
# also prints a big number,
# but doesn't hit the recursion limit.

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

setq

Дата 6.3.2006, 12:22 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

Цитата(Void @ 5.3.2006, 23:47

)

по ссылке с этого поста в ЖЖ

и каменты интересные)

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Python: Общие вопросы \| Следующая тема »