🚀 go-pugleaf

Re: iteration vs recursion in C, Scheme, and Logo

In my own humble experience the choice seems to lie on whether the
programmer believes a particluar expressive style "works" in a given
language. That's a function both of training and experience.

It's not enough to know that a particular form of expression (say,
recursive forumlations of algorithms) is supposed to work in a
language, one also has to be familiar with how the behavior manifests
itself, especially at bug/crash time. That's why the guy griped about
needing "1 meg of stack space" in C to allow recursion.

Having spent most of my professional life switching randomly between
recursive and iterative formulations, I tend to lean towards recursion
when I need to express something clearly and concisely. I really think
recursion is easier to use than iteration when trying to frame a problem
solution. 

However, recursion has pretty nasty boundary behavior, i.e., when you
reach the limits of your machinery, recursive solutions suffer stack
overflow. It's hard to write code that can self diagnose the problem
that caused the stack overflow (which action or user expression really
caused it?) and recover in a clean manner. Thus, production programs that
get used by others generally must use recursion very, very carefully
if at all.

I think recursion is a terrific teaching and reasoning tool. It
encourages the sort of problem abstraction that leads to modular
programming style.  It lets you solve more problems with fewer
variables.  The only 'problem' with it is that it's not taught at a
sufficiently introductory level, with a few notable exceptions. It's
going to take a few educational generations for that to change, if it
ever does.

I suspect the "right" way to teach programming is to start with
recursion as the essential iterative technique, and then teach
how to convert from recursive to iterative as an engineering task.

Rick.
smith@sctc.com          arden hills, minnesota