How explain why Python is easier/nicer than Lisp which has a simpler grammar/syntax?

Chris Angelico rosuav at gmail.com
Fri Aug 7 17:02:46 EDT 2020


On Sat, Aug 8, 2020 at 6:34 AM Terry Reedy <tjreedy at udel.edu> wrote:
>
> 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.

I'm aware you can do recursion iteratively and iteration recursively,
but why WOULD you ever do this? The version you've shown here isn't
any more elegant than the purely iterative version, and all it's doing
is implementing a for loop using recursive calls. (Also, it has one
thing that rankles with me, and that's a function signature that is
intentionally different for the recursive calls as for the main call.
You should *never* pass the 'pair' parameter on the initial call, and
it will *always* be passed on the recursive calls.) The idiomatic
recursive version is not tail recursive. Same with the idiomatic
recursive merge sort, which does forking recursion and then tail-calls
the merge operation. (Or you can implement the merge inline, but
whenever I'm explaining it, I prefer to write merge() as a separate
function.)

Knowing how to translate recursion into iteration and vice versa is a
useful skill (picture this: you're trying to build some actual coded
logic into an alias expansion system, where the only conditional you
have is "execute this file" with text substitution in the file name,
and the only looping you have is to re-execute the same file), but
it's not the way to show off the beauty of recursion.

ChrisA


More information about the Python-list mailing list