On Sat, Aug 8, 2020 at 2:44 AM Richard Damon <rich...@damon-family.org> wrote:
>
> On 8/7/20 11:46 AM, Chris Angelico wrote:
> > My point is that doing Fibonacci recursively is arguably more elegant
> > while being materially worse at performance, but there are other
> > examples that are fundamentally recursive, are just as elegant (merge
> > sort: "fracture the array in half, sort each half, then merge them"),
> > and can't be done better iteratively. So IMO Fibonacci is a flawed
> > demonstration of what is a very valid point ("recursion can be really
> > elegant"), and other examples would serve the purpose better.
>
> I would say that doing the recursive Fibonacci version can be an
> important step (near the end) of the recursion unit as a learning
> experience on some of the dangers of recursion (like turning an O(N)
> problem into O(2**N). It perhaps can lead to discussions on optimization
> techniques (like caching results) that can alleviate some of the issues
> (at other costs).
Yes, I'd definitely agree. It's great to have some demonstrations of
the advantages and disadvantages of recursion, and Fibonacci offers
both in one tidy package :)
Here's another really great example: triangle numbers.
def tri(n):
if n < 1: return 0
return n + tri(n - 1)
def tri(n):
tot = n
for i in range(n):
tot += i
return tot
def tri(n):
return functools.reduce(operator.add, range(n + 1))
def tri(n):
return n * (n + 1) // 2
A great demo of different ways to think about the same problem, with a
nice O(1) reference at the end that you can validate them against :)
ChrisA
--
https://mail.python.org/mailman/listinfo/python-list
