Terry Reedy schreef op 7/08/2020 om 22:08:
On 8/7/2020 11:46 AM, Chris Angelico wrote:

My point is that doing Fibonacci recursively is arguably more elegant
while being materially worse at performance.

This is a common misconception.  Linear iteration and tail recursion are
equivalent.  The issue is calculating values once versus multiple times.
   Here is the fast recursion equivalent to the fast iteration.

def fib(n, pair=(1,0)):
     previous, current = pair
     if n:
        return fib(n-1, (current, previous + current))
     else:
        return current

Of course, but now you've lost the elegance of the recursive version being near-literal translation of the mathematical definition.

It's a gripe I have with many introductory texts to functional programming. Recursion is super cool, they say, it lets you decompose problems in smaller problems in an elegant natural way. But then show examples like Fibonacci where the elegant natural way is a bad solution, so they introduce accumulators and stuff, and then Fibonacci does work much better indeed. But they fail to notice that the new solution is not elegant and natural at all anymore. It has just become iteration in a recursive disguise.

I'm not saying there is nothing useful in functional programming and the use of recursion; there most certainly is. But the way many texts introduce it IMO doesn't help at all to understand the elegance that can be achieved.

--
"Honest criticism is hard to take, particularly from a relative, a
friend, an acquaintance, or a stranger."
        -- Franklin P. Jones

Roel Schroeven

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

Reply via email to