From: Joel Wilsson <siigron@...>
Date: 2001-09-23T01:28:44+09:00
Subject: [ruby-talk:21547] Re: Math and Programming

Seems like no-one else will answer this, so I guess I'll "have to".
I'm pretty new to Scheme (it's through Scheme I learned about proper
tail-recursion), so I could be wrong on some points.
If there are any LISP gods here, feel free to correct me.

> 1. Someone made a mention of Ruby being "properly tail-recursive".
> What's the definition of "properly tail recursive"? I've heard the term
> before, but I'm not sure what it means.  In every language I've coded
> in, functions can call themselves; is this all that the term means? Or
> is it something more?

It's a bit more than that. It has to do with the way the functions call
themselves.

> 2. My impression of recursion has been that it ought to be used only in
> cases where the function can only recurse a predictable, reasonably
> small number of times; otherwise the stack will overflow eventually.
> The "factorial" function in the examples seems to break that rule.  Is
> this safe?  If so, why?

Yes, overflowing the stack is the reason why recursion isn't always the
best way to solve a problem.
Tail-recursion solves the problem of overflowing the stack by not
allocating a new stack unless it has to.
If the last thing a function does is call itself, there is no need to
keep the old stack - the current stack can be re-used for the new
call.

# returns the set of numbers between (and including) "s"tart to "e"nd
def enumerate(s, e, list)
   if s > e
     return list
   end
   list.push s
   enum(s + 1, e, list)
end
l = enum(0, 10, [])
p l

the important thing to note is that the stack used for the first function
call can be re-used for the next recursive call, because we don't need any
information from the previous call except for the parameters.
since we have the same number of parameters, we can just put the
parameters on the old function call stack and restart the function with
the new parameters.
In Scheme (and other LISP dialects) there are no local variables, so all
functions that end in a call to themselves can re-use the previous
function call stack - since there is only one active stack, in a function
that is properly tail-recursive, you can't overflow it.
The reason the recursive factorial function (can't remember who posted
it) wasn't tail-recursive was that it didn't end in just a call to
itself, it ended in a call like "n * factorial(n - 1)", which means we
have to return to that function call stack to be able to do the
multiplication.

> 3. Todd: Since you have such a high respect for math (and you quoted
> heinlein :-), do you have any book recommendations for someone desiring
> to learn the formal mathematics that relate to programming?  
>
> -- Avdi Grimm
>

Regards,
       Joel Wilsson