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
