How explain why Python is easier/nicer than Lisp which has a simpler grammar/syntax?
Chris Angelico
rosuav at gmail.com
Fri Aug 7 02:23:42 EDT 2020
On Fri, Aug 7, 2020 at 11:11 AM Python <python at bladeshadow.org> wrote:
> Not necessarily. Some problems very naturally lend themselves to
> recursive solutions. Fibonacci's sequence is one.
>
> #!/usr/bin/python
>
> def fib(x):
> if x < 1:
> raise "arg must be >= 1"
> if x == 1:
> return 0
> elif x == 2:
> return 1
> else:
> return fib(x - 1) + fib(x - 2)
>
> Pretty straightforward. Now try yourself to write the iterative
> version.
It might look slightly better to a mathematician, but it's so
abysmally inefficient (unless you add extra layers of indirection)
that it's not really a good example. The iterative version seeds the
algorithm and lets it run:
def fib(x):
if x < 1: raise ValueError
last, cur = 0, 1
for _ in range(1, x):
last, cur = cur, last + cur
return cur
It needs a way of remembering the previous as well as the current,
whereas the recursive one needs to ask to calculate the previous and
previous-by-two. I'll leave it to you whether that's better or worse.
But if you want something that is massively more elegant when done
recursively, the best place to look is an inherently recursive data
structure. How do you process all files in a directory tree?
def process(dir):
for thing in dir:
if is_file_we_want(thing): use_thing(thing)
if is_dir(thing) process(thing)
Now THAT is recursion at its best. Of course it's possible to do it
iteratively, but it won't be anything like this clean. There's a
reason that directory tree operations are usually called "recursive"
(eg "rm -r" means "remove directories and their contents recursively",
per the man page).
Similarly, quick sort and merge sort are beautiful when written recursively:
def mergesort(list):
if len(list) < 2: return list
mid = len(list) // 2
left = mergesort(list[:mid])
right = mergesort(right[mid:])
return merge(left, right)
I think recursion looks best when it's doing multiple levels at once
(eg "sort the left, sort the right"), rather than just a single one
(factorial being "n * factorial(n - 1)"), since it's a lot harder to
create an elegant iterative version of multiple recursion. The
Fibonacci example is a bit of an outlier, as the recursive one is just
*so bad* in performance that it loses some elegance points, but the
other examples don't suffer from that, and they're still very clean.
ChrisA
More information about the Python-list
mailing list