It was already done: https://pypi.org/project/tail-recursive/
On Thu, 30 Dec 2021 at 16:00, hongy...@gmail.com <hongyi.z...@gmail.com> wrote: > > I try to compute the factorial of a large number with tail-recursion > optimization decorator in Python3. The following code snippet is converted > from the code snippet given here [1] by the following steps: > > $ pyenv shell datasci > $ python --version > Python 3.9.1 > $ pip install 2to3 > $ 2to3 -w this-script.py > > ``` > # This program shows off a python decorator( > # which implements tail call optimization. It > # does this by throwing an exception if it is > # its 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 its 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 as 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. > ``` > However, when I try to test the above script, the following error will be > triggered: > ``` > $ python this-script.py > Traceback (most recent call last): > File "/home/werner/this-script.py", line 32, in func > return g(*args, **kwargs) > File "/home/werner/this-script.py", line 44, in factorial > return factorial(n-1, n*acc) > File "/home/werner/this-script.py", line 28, in func > raise TailRecurseException(args, kwargs) > TypeError: exceptions must derive from BaseException > > During handling of the above exception, another exception occurred: > > Traceback (most recent call last): > File "/home/werner/this-script.py", line 46, in <module> > print(factorial(10000)) > File "/home/werner/this-script.py", line 33, in func > except TailRecurseException as e: > TypeError: catching classes that do not inherit from BaseException is not > allowed > ``` > > Any hints for fixing this problem will be highly appreciated. > > [1] https://stackoverflow.com/q/27417874 > > Regards, > HZ > -- > https://mail.python.org/mailman/listinfo/python-list -- https://mail.python.org/mailman/listinfo/python-list
