🚀 go-pugleaf

Rick Smith writes:
>Re: iteration vs recursion in C, Scheme, and Logo
> [...]
>However, recursion has pretty nasty boundary behavior, i.e., when you
>reach the limits of your machinery, recursive solutions suffer stack
>overflow.

It's funny that you refer to reaching your memory limit as "boundary
behavior", because when I first read your article I thought you were going
to say that writing a program recursively makes it difficult to get the
boundary conditions right.  That's not what you said, of course, but it
brings up another point in the recursion/iteration thread...

IMHO, writing a function recursively makes it incredibly easier to get the
boundary conditions right.

int Factorial(int x) {
    int result;
    result = 1;
    while (x > 0) {
	result *= x;
	x--;
    }
    return result;
}

Should you initialize result to 1 or 0?  Is it while x >0 or x >= 0, or 
x > 1 ?  Don't forget to decrement x each time you loop...  etc, etc...


TO FACTORIAL :X
IF :X = 0 [OUTPUT 1]
OUTPUT :X * FACTORIAL :X -1
END

In the recursive version, the only thinking you have to do about boundary
conditions is in the base case.  Furthermore, it's much easier to think
about, because instead of framing it as "what exactly will the computer do
when?" you can just ask yourself "what's 0 factorial?"

(Apologies to Brian Harvey for not writing the WHILE version in Logo; I
don't remember the syntax of the Logo WHILE he made up in CSLS...)

>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.

You mean, start with recursion as the essential iterative (and
non-iterative) technique, and then teach how to do tail-recursion
elimination when you take a compiler construction class in college.  :-)

-Matt