How explain why Python is easier/nicer than Lisp which has a simpler grammar/syntax?
Terry Reedy
tjreedy at udel.edu
Fri Aug 7 16:08:06 EDT 2020
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
for i in range(10): print(fib(i), end=' ')
# 0 1 1 2 3 5 8 13 21 34
One can also do the slow algorithm, with wasteful duplication,
iteratively with one or two stacks of values instead of the hidden stack
of execution frames. I don't remember the details right now without
checking a text.
--
Terry Jan Reedy
More information about the Python-list
mailing list