[Tutor] recursion

[avi.e.gross at gmail.com]

Good points, Dave.

I see a hybrid method that might satisfy lots of needs.

You start with a generator with a name like next_fib() that returns one
number at a time, say starting with 0 then 1 and so on.

You can then make another function (perhaps a generator, perhaps not) that
does whichever other thing you want. The example of giving the 10th simply
would call next_fib as many times as needed then return just the last value.
If you want ten at a time, it would gather the results of ten calls and
bundle them, and if called again get the next ten. 

What gets me about the similar but different factorial issue is that in real
life, and I mean things like game theory looking at permutations and
combinations, the factorials get HUGE and anyone doing it by hand notices
that something like 

(n!) / ((n-k)! * k!)

Can often be handled better by canceling out  lots of stuff and only
calculating what is left. It really is not a great idea unless you use
extended integers to calculate 52!/(32!20!) or even bigger numbers so what
you almost want is to take the larger of the two in the denominator (in this
case 32!) and calculate the product of range() from 52 to 33 only. I do that
in an example below using functools.reduce() to do the arbitrary length
multiplication since numpy.prod() normally uses regular integers that
overflow!

import math
from functools import reduce

print("combinations of 52 cards taken 32 at a time or whatever.\n")
print("first showing 52!, then 32!, then 20! then 52!/(32!*20!)")
print(math.factorial(52))
print(math.factorial(32))
print(math.factorial(20))
result1 = math.factorial(52)//(math.factorial(32)*math.factorial(20))
print(result1)

print("Now do a similar calculation but simpler by canceling out 32! and
using")
print("range(52,32, -1) and taking the product of that. Finally show that
divided by 20!")
print(list(range(52, 32, -1)))
quasi_factorial = reduce(lambda x, y: x* y, range(52, 32, -1), 1)
print(quasi_factorial)
result2 = quasi_factorial // math.factorial(20) 
print(result2)

I will show the output below but my guess is that for large values of N this
tends to be more computationally efficient as it avoids making some
humungous integers as factorial alone can be expensive unless my method of
using reduce with an anonymous function is too expensive.

Output from running python within RSTUDIO:

>>> import math
>>> from functools import reduce
>>> 
>>> print("combinations of 52 cards taken 32 at a time or whatever.\n")
combinations of 52 cards taken 32 at a time or whatever.

>>> print("first showing 52!, then 32!, then 20! then 52!/(32!*20!)")
first showing 52!, then 32!, then 20! then 52!/(32!*20!)
>>> print(math.factorial(52))
80658175170943878571660636856403766975289505440883277824000000000000
>>> print(math.factorial(32))
263130836933693530167218012160000000
>>> print(math.factorial(20))
2432902008176640000
>>> result1 = math.factorial(52)//(math.factorial(32)*math.factorial(20))
>>> print(result1)
125994627894135
>>> 
>>> print("Now do a similar calculation but simpler by canceling out 32! and
using")
Now do a similar calculation but simpler by canceling out 32! and using
>>> print("range(52,32, -1) and taking the product of that. Finally show
that divided by 20!")
range(52,32, -1) and taking the product of that. Finally show that divided
by 20!
>>> print(list(range(52, 32, -1)))
[52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34,
33]
>>> quasi_factorial = reduce(lambda x, y: x* y, range(52, 32, -1), 1)
>>> print(quasi_factorial)
306532583223109543994300006400000
>>> result2 = quasi_factorial // math.factorial(20) 
>>> print(result2)
125994627894135

Clearly the output is the same. (Note my original version converted the darn
output of both calculations because of the darn division from unrestricted
integer to float ending in .0 so I changed it to integer division using //
but the point remains that using factorial on large numbers may work better
using shortcuts like the above that I cobbled together or perhaps even
better ones like making a class that works a bit like a fraction module
where you can operate on two series of numbers representing a numerator and
denominator and keep finding ways to say see a 32 on top and a 16 on bottom
and divide both the same way such as by two or even sixteen until you have
reduced them so they retain little in common that cannot be factored out.
The result can finally be multiplied out in both top and bottom and a final
division done without huge intermediate numbers along the way.

Then again, python does support huge integers where many other languages
restrict them to 64 bits and there are also limits on how big a floating
point number can be.






-----Original Message-----
From: Tutor <tutor-bounces+avi.e.gross=gmail.com at python.org> On Behalf Of dn
Sent: Monday, August 15, 2022 7:51 PM
To: tutor at python.org
Subject: Re: [Tutor] recursion

On 16/08/2022 11.23, Alan Gauld via Tutor wrote:
> On 15/08/2022 18:19, Mats Wichmann wrote:
> 
>>> There are things like traversing trees which are harder to do 
>>> without recursion but Fibonacci is absolutely trivial to do
> 
> The other common recursion function is factorial() and that too is 
> nearly trivial to do non-recursively. But traversing trees etc and 
> other real-world uses of recursion are a lot harder to teach! (You 
> need to teach trees for a start!)
> 
> I suspect the problem is that recursio is introduced too early in the 
> curriculum, but teachers like it because it's cool from an academic 
> standpoint and can help teach a regular approach to designing 
> programs.
> (see the online book "How to Design Programs" for an example of the 
> approach...http://htdp.org)


Does the recursion/iteration decision also depend upon the definition of the
'result' from Fibonacci?

Is the objective to find a single value?
- the next Fibonacci number
- the tenth Fibonacci number
- the first Fibonacci number larger than 10

Alternately, is the objective to find a group:
- the first ten Fibonacci numbers
- the next ten Fibonacci numbers
- ten Fibonacci numbers larger than 10
(feels a bit contrived!)

A recursive method will handle the first category happily. However, cannot
handle the second without repeated calls to populate a list - and one
hopes/assumes, some "memoisation" - which is itself, effectively, a list.


However, when there is much (much) more to the script, and the Fibonacci but
a small part, having a list could become 'expensive'. More importantly to
code-design, the list-creation will likely occur 'at the front end' and
(thus) dislocated from where it is used (cohesion, coupling, independence,
interdependence, code-organisation, ...).

Unlike many?most other programming-languages, Python offers the generator
option (ie iteration as generation) which will answer both of the above
categories, and places the (?self-documenting) call right in the midst of
'the action' without unnecessary distraction!

Accordingly, the preference (@Mats), and the curriculum/temptation idea
(@Alan). What 'they' do should not define what 'we' do/can do!
--
Regards,
=dn
_______________________________________________
Tutor maillist  -  Tutor at python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor