[Tutor] recursion

[avi.e.gross at gmail.com]

Mats,

I assume you are talking about how recursion to unlimited depths is not a
great scheme. Does Python support any form of tail recursion?

I have seen some attempts with a similar factorial function that might be
called quite often in a program calculating something like probabilities in
card games, that a wrapper can be used that stores results of earlier calls
and when asked yet again for 51! It simply returns the previous value and
avoids a cascade of many nested function calls. But that too can have an
increasing cost if you end up storing lots of calls. Luckily higher
factorials tend to overflow except in Python with unlimited sized integers!

My favorite totally silly recursion over-reach was in a LISP program from
The Little Lisper that tried to show the mathematical meaning of what it
means in a number system for something (non-negative) being greater than
something else (non-negative).

In English, they defined greater(alpha, omega) this way:

- If alpha is zero, return that omega was greater than or equal. 
- Else if omega is zero, return that it was greater than or equal.
- Else, if both alpha and omega are not zero, recursively call greater(alpha
- 1, omega - 1) and whatever it returns, return that upwards as your value.

This works OK for greater(3,5) but not real well for greater(1_000_000_000,
666_666_666_666) which on most machines will end up with billions of paused
functions on the stack UNLESS you implement tail recursion so that each
function replaces the single function on the stack when it is called.

Programming and mathematical elegance sometimes go together and other times,
are a bit much.

But, to be fair, many ideas start with a simplified model as that is all
people can handle, but over time more and more complexity is allowed until
at some point we have useful tools that allow rather arbitrary data
structures. I mean some things are easy to do as lists and then as say
data.frames and then as arbitrarily nested formats like XML that generate
sort of treelike structures with no restrictions on the branching but then
you move to things like neural networks where feedback can move back and
forth and find a generalized graph with no restrictions can be handled.

Back to tutor, I wonder if someone out there has implemented the Fibonacci
sequence calculation in every language I know and also in every language I
don't know!

I suspect they may have overlooked the one I wrote so many years ago in a
language called nroff/troff that was supposed to do typesetting but in order
to do that, allowed some arithmetic ...

Yep, a quick search shows, ...


-----Original Message-----
From: Tutor <tutor-bounces+avi.e.gross=gmail.com at python.org> On Behalf Of
Mats Wichmann
Sent: Sunday, August 14, 2022 7:05 PM
To: tutor at python.org
Subject: Re: [Tutor] (no subject)

On 8/14/22 16:37, dn wrote:
> On 15/08/2022 04.48, Phindile Julia wrote:
>> Hey how to create a Fibonacci list?
> 
> 
> Hi Phindile,
> Is this your first post to the list? Welcome!
> 
> We volunteer help to learners (and Tutors) who are getting to grips 
> with Python. We will help *you* to learn Python and how best to use 
> it, but won't give 'homework' answers (wouldn't that be the 
> exact-opposite of 'you learning'?)
> 
> As it happens, I am currently drafting a coding-challenge, which will 
> feature a Fibonacci 'engine' to generate data. So, will be happy to 
> take a look at your code so-far and offer a critique.

The Fibonacci sequence is fascinating in its own right, but the topic is
often used to teach recursion to programming students where is it often hard
to explain "why would I want to do that?" - Fibonacci provides one of the
clearer ways to describe it.

It can also be used to illustrate some pretty advanced Python and computer
science topics - mainly because the more numbers you try to generate with
the "most obvious" implementation the slower it gets - and it gets slow
quite rapidly, so this is also a fruitful field for optimization strategies.
I mention this because while we here try to be as helpful as possible, we
sometimes get a bit carried away discussing nuances - so take what you need
from answers based on where you are in your learning path, and feel free to
tune us out in case the discussion ends up going on!!
_______________________________________________
Tutor maillist  -  Tutor at python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor