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

On Thursday, December 30, 2021 at 9:04:36 PM UTC+8, hongy...@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.

See here [1] for the related discussion.

[1] https://discuss.python.org/t/typeerror-catching-classes-that-do-not-inherit-from-baseexception-is-not-allowed/12800

HZ

On Fri, Dec 31, 2021 at 2:00 AM hongy...@gmail.com
<hongyi.zhao@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
>

If it's an exception, it needs to subclass Exception or BaseException.

(Also, is this REALLY an optimization? Exception handling isn't the
fastest. Yes, it avoids some measure of recursion depth, but it looks
like a pretty inefficient way to do things. Python is not Lisp, and
there are very very few algorithms that actually benefit from tail
call optimization that wouldn't benefit far more from other ways of
doing the same thing.)

ChrisA

On Fri, Dec 31, 2021 at 2:03 AM hongy...@gmail.com
<hongyi.zhao@gmail.com> wrote:
> See here [1] for the related discussion.
>
> [1] https://discuss.python.org/t/typeerror-catching-classes-that-do-not-inherit-from-baseexception-is-not-allowed/12800

Why did you post in two places at once? Did you need more people to
tell you the same thing as the error message?

ChrisA

On Thursday, December 30, 2021 at 11:24:20 PM UTC+8, Chris Angelico wrote:
> On Fri, Dec 31, 2021 at 2:03 AM hongy...@gmail.com
> <hongy...@gmail.com> wrote:
> > See here [1] for the related discussion.
> >
> > [1] https://discuss.python.org/t/typeerror-catching-classes-that-do-not-inherit-from-baseexception-is-not-allowed/12800
> Why did you post in two places at once? Did you need more people to
> tell you the same thing as the error message?

Doing so may attract the attention of developers, such as increasing the content of traceback information to make troubleshooting easier, just as André Roberge says here [1].

[1] https://discuss.python.org/t/typeerror-catching-classes-that-do-not-inherit-from-baseexception-is-not-allowed/12800/6?u=hongyi-zhao

> ChrisA

HZ

On Thursday, December 30, 2021 at 11:23:35 PM UTC+8, Chris Angelico wrote:
> If it's an exception, it needs to subclass Exception or BaseException.

I see. That is, the following:

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

> (Also, is this REALLY an optimization? Exception handling isn't the
> fastest. Yes, it avoids some measure of recursion depth, but it looks
> like a pretty inefficient way to do things. Python is not Lisp, and
> there are very very few algorithms that actually benefit from tail
> call optimization that wouldn't benefit far more from other ways of
> doing the same thing.)

Could you give some examples of the other methods you mentioned above?
> ChrisA

HZ

On Fri, Dec 31, 2021 at 9:42 AM hongy...@gmail.com
<hongyi.zhao@gmail.com> wrote:
>
> On Thursday, December 30, 2021 at 11:24:20 PM UTC+8, Chris Angelico wrote:
> > On Fri, Dec 31, 2021 at 2:03 AM hongy...@gmail.com
> > <hongy...@gmail.com> wrote:
> > > See here [1] for the related discussion.
> > >
> > > [1] https://discuss.python.org/t/typeerror-catching-classes-that-do-not-inherit-from-baseexception-is-not-allowed/12800
> > Why did you post in two places at once? Did you need more people to
> > tell you the same thing as the error message?
>
> Doing so may attract the attention of developers, such as increasing the content of traceback information to make troubleshooting easier, just as André Roberge says here [1].
>

It's a simple question with a simple answer. You don't need to
cross-post. All you do is split the discussion so people don't know
what's already been said.

ChrisA

On Fri, Dec 31, 2021 at 9:42 AM hongy...@gmail.com
<hongyi.zhao@gmail.com> wrote:
> > (Also, is this REALLY an optimization? Exception handling isn't the
> > fastest. Yes, it avoids some measure of recursion depth, but it looks
> > like a pretty inefficient way to do things. Python is not Lisp, and
> > there are very very few algorithms that actually benefit from tail
> > call optimization that wouldn't benefit far more from other ways of
> > doing the same thing.)
>
> Could you give some examples of the other methods you mentioned above?
>

If you have a function that has just a single tail call site, there's
usually no point writing it recursively.

def factorial(n):
ret = 1
for i in range(1, n + 1): ret *= i
return ret

def fibonacci(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a

Neither of these wants to be recursive, and writing them recursively
pollutes the function signature with parameters that really exist just
to be local variables. Passing an accumulator down is a terrible way
to demonstrate the beauty of recursion - it instead shows off how you
can shoehorn anything into recursion and make it worse in the process.

Please, everyone, stop trying to optimize the wrong things.

Write good code, don't try to make bad code stop crashing.

ChrisA

On Friday, December 31, 2021 at 7:04:24 AM UTC+8, Chris Angelico wrote:
> Neither of these wants to be recursive, and writing them recursively
> pollutes the function signature with parameters that really exist just
> to be local variables. Passing an accumulator down is a terrible way
> to demonstrate the beauty of recursion - it instead shows off how you
> can shoehorn anything into recursion and make it worse in the process.

Then what cases/scenarios can demonstrate the beauty of recursion?

HZ

Chris Angelico <rosuav@gmail.com> writes:
> writing them recursively pollutes the function signature with
> parameters that really exist just to be local variables.

It's idiomatic in a coding style that considers non-constant variables
to be problematic in their own right. Of course you can use an
auxiliary function to get rid of the extra parameter to the outer
function. I don't see the GP post so I don't know if the posted example
did that. Anyway, one can at most say that traditional Python style
prefers variables and loops to recursion. Others like to say: "to
iterate is human; to recurse, divine". ;-)

On 2021-12-30 23:27, hongy...@gmail.com wrote:
> On Friday, December 31, 2021 at 7:04:24 AM UTC+8, Chris Angelico wrote:
>> Neither of these wants to be recursive, and writing them recursively
>> pollutes the function signature with parameters that really exist just
>> to be local variables. Passing an accumulator down is a terrible way
>> to demonstrate the beauty of recursion - it instead shows off how you
>> can shoehorn anything into recursion and make it worse in the process.
>
> Then what cases/scenarios can demonstrate the beauty of recursion?
>
Walking a tree.

On Friday, December 31, 2021 at 7:50:48 AM UTC+8, MRAB wrote:
> On 2021-12-30 23:27, hongy...@gmail.com wrote:
> > On Friday, December 31, 2021 at 7:04:24 AM UTC+8, Chris Angelico wrote:
> >> Neither of these wants to be recursive, and writing them recursively
> >> pollutes the function signature with parameters that really exist just
> >> to be local variables. Passing an accumulator down is a terrible way
> >> to demonstrate the beauty of recursion - it instead shows off how you
> >> can shoehorn anything into recursion and make it worse in the process.
> >
> > Then what cases/scenarios can demonstrate the beauty of recursion?
> >
> Walking a tree.

There are many type of trees. Do you mean all of them?

Beauty of Recursion?

Well, there is what I call Mathematical Beauty, and then there is reality.

It is fantastic to prove neat theorems that something is possible by methods
like mathematical induction that in some sense use recursion as in if
something is true for some base value and it can be shown that if it is true
for N then it also is true for N+1, then by a sort of recursion, it is true
for every larger value!

And, yes, you can write some seemingly neat and compact routines using
recursion, but there are many run-time costs as Chris and others can
suggest.

Where is recursion most useful? I can think of many places but will briefly
mention a few.

There is a recursive sort algorithm that keeps dividing the data it is
handled in two and calls itself recursively to process the first half and
then again on the second half and simply merges the sorted results and
returns that. Clearly this kind of algorithm calls itself to a depth of
about log to the base two times. And a possible advantage here is that this
can take some advantage of parallel architectures and some simultaneity.

Another general set of recursive applications is anything that wanders
tree-structures and looks for items or places new items in an appropriate
place. If it is a binary tree, there is a slight similarity with my first
example as there is a do_left and a do_right type of recursion but not
really. And of course trees can have more than two branches and you can use
recursion on other complex structures. But in some cases, you can come up
with a non-recursive way to do things by keeping track of where you are and
where you have been.

Recursion is a good thing to teach but also a horrible thing when misused. A
book I read decades ago, called The Little Lisper, showed algorithms such as
asking for greater(A, B) to be done sort of like by recursively calling
greater(subtract1(A), subtract1(B)) as long as neither A nor B becomes zero.
Neat algorithm and tolerable for greater(3,5) returning 5 after a few
recursions when 3 has been lowered to zero. Not so good with negative
numbers. But greater(10000000000, 10000000001) might take a while and your
machine may run out of memory and since you want to return the original
value, tail recursion may not be enough unless you modify things a bit such
as using a helper function that also includes the original numbers so it
returns the right one or ...

Many machines simply restrict you to compare numbers only up to the point
where an int or float of some kind support it and then the operation of
comparison is mostly just done in a few steps in the hardware no matter what
size the two things are. Python with support for unlimited size integers
though, ...

-----Original Message-----
From: Python-list <python-list-bounces+avigross=verizon.net@python.org> On
Behalf Of hongy...@gmail.com
Sent: Thursday, December 30, 2021 6:27 PM
To: python-list@python.org
Subject: Re: builtins.TypeError: catching classes that do not inherit from
BaseException is not allowed

On Friday, December 31, 2021 at 7:04:24 AM UTC+8, Chris Angelico wrote:
> Neither of these wants to be recursive, and writing them recursively
> pollutes the function signature with parameters that really exist just
> to be local variables. Passing an accumulator down is a terrible way
> to demonstrate the beauty of recursion - it instead shows off how you
> can shoehorn anything into recursion and make it worse in the process.

Then what cases/scenarios can demonstrate the beauty of recursion?

HZ
--
https://mail.python.org/mailman/listinfo/python-list

It was already done: https://pypi.org/project/tail-recursive/

On Thu, 30 Dec 2021 at 16:00, hongy...@gmail.com <hongyi.zhao@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

Am Thu, Dec 30, 2021 at 03:57:25PM -0800 schrieb hongy...@gmail.com:

> > > Then what cases/scenarios can demonstrate the beauty of recursion?
> > >
> > Walking a tree.
>
> There are many type of trees. Do you mean all of them?

Palm trees don't lend themselves to recursion all that much.

Karsten
--
GPG 40BE 5B0E C98E 1713 AFA6 5BC0 3BEA AC80 7D4F C89B

I am sure some people have a sense of humor, but anyone on this forum who
actually does not have some idea of what various "tree" data structures are
in computer science, probably won't get any replies from me when asking such
questions.

But indeed there are things closer to classical trees that are traversed in
various ways including depth-first versus breadth first. Some have special
names like a parse tree or a decision tree and they can even be collected
into a random forest.

But fundamentally, the idea of using a recursion that at each node may take
multiple next steps by calling an instance of itself at the new node, is
fairly common, as are using it to search many kinds of data structures.

The discussion though suggests that no single idea about computer languages
need be used constantly and sometimes recursion is not the only method or
even the best method. You can design tree structures in ways that allow them
to be traversed in an iterative way such as having bi-directional links
along with flags that mark where you entered a node from or already visited.
Tools should be tools, not religions.

-----Original Message-----
From: Python-list <python-list-bounces+avigross=verizon.net@python.org> On
Behalf Of Karsten Hilbert
Sent: Friday, December 31, 2021 7:09 AM
To: python-list@python.org
Subject: Re: builtins.TypeError: catching classes that do not inherit from
BaseException is not allowed

Am Thu, Dec 30, 2021 at 03:57:25PM -0800 schrieb hongy...@gmail.com:

> > > Then what cases/scenarios can demonstrate the beauty of recursion?
> > >
> > Walking a tree.
>
> There are many type of trees. Do you mean all of them?

Palm trees don't lend themselves to recursion all that much.

Karsten
--
GPG 40BE 5B0E C98E 1713 AFA6 5BC0 3BEA AC80 7D4F C89B
--
https://mail.python.org/mailman/listinfo/python-list