Scheme - Tail Recursion, Take 2

Author

Tail Recursion, Take 2

2006-01-19, 4:08 am

After previous discussion of tail recursion, I was investigating it in
other languages. ( Note: this post has no Scheme, but concepts learned
in Scheme are applied elsewhere, which I think is one of the key points
of the language). Anyhow:

I found a page that had a snippet about tail recursion:
http://danzig.jct.ac.il/cpp/recursion.html
Here is some text off the page:
" What is the difference between these to examples:

return x * factorial(x - 1);

return factorial(x - 1) * x;

Tail recursion is defined as occuring when the recursive call is at the
end of the recursive instruction. This is the case with the first of
our factorial solutions above. It is useful to notice when ones
algorithm uses tail recursion because in such a case, the algorithm can
usually be rewritten to use iteration instead. In fact, the compiler
will (or at least should) convert the recursive program into an
iterative one. This eliminates the potential problem of stack overflow.
"

In my mind, unlike the author's, /neither/ of these are tail-recursive,
because they both involve the tiny people inside the computer twiddling
their thumbs waiting for each other*. The recursion in both cases winds
itself up and then unwinds.. A tail-recursive factorial call would only
wind. It would contain all of the necessary information at each step:

return factorial(x-1, soFar);

where soFar contains the result of the previous steps and gets
increased by x+1 each time. This is what I think of when I think of
"tail recursion."

Who is right, me or this other person?

* This is such a corny metaphor I feel silly using it. At the moment,
it's the language I have, so I'll use it. I didn't make it up.

Pascal Bourguignon

2006-01-19, 4:08 am

"H." <hbe123@gmail.com> writes:
> [...]
> return factorial(x-1, soFar);
>
> where soFar contains the result of the previous steps and gets
> increased by x+1 each time. This is what I think of when I think of
> "tail recursion."
>
> Who is right, me or this other person?

You are right, obviously.

--
__Pascal Bourguignon__ http://www.informatimago.com/

PLEASE NOTE: Some quantum physics theories suggest that when the
consumer is not directly observing this product, it may cease to
exist or will exist only in a vague and undetermined state.

Anton van Straaten

2006-01-19, 4:08 am

H. wrote:
> In my mind, unlike the author's, /neither/ of these are tail-recursive,
> because they both involve the tiny people inside the computer twiddling
> their thumbs waiting for each other*. The recursion in both cases winds
> itself up and then unwinds.. A tail-recursive factorial call would only
> wind. It would contain all of the necessary information at each step:
>
> return factorial(x-1, soFar);
>
> where soFar contains the result of the previous steps and gets
> increased by x+1 each time. This is what I think of when I think of
> "tail recursion."
>
> Who is right, me or this other person?

You are.

It's common for programmers in non-Lisp languages to ignore the
semantics of built-in, infix operators, like '*' in the given example.
In Lisp-like languages, it's clearer that there's no significant
difference between:

(* x (factorial (- x 1)))
and
(* (factorial (- x 1)) x)

In both cases, both arguments must be evaluated before the call to '*',
which means that neither call to 'factorial' is tail-recursive as it stands.

Languages with infix syntax don't change this basic fact about the way
such expressions are evaluated, they just hide it better. This is one
of the reasons that learning Scheme can help make you a better
programmer in other languages -- it teaches you to see beneath the
surface syntax that can obscure the semantics of other languages.

> * This is such a corny metaphor I feel silly using it. At the moment,
> it's the language I have, so I'll use it. I didn't make it up.

Yeah, "tiny people" is a little silly. You should really call them
"leprechauns". ;-)

More seriously, later on, you'll learn to call some of them
"continuations". Enjoy the simplicity while it lasts!

Anton

2006-01-19, 4:08 am

> It's common for programmers in non-Lisp languages to ignore the
> semantics of built-in, infix operators, like '*' in the given example.

The

part is that this isn't just a programmer; it's a teacher! The
site of the page says:"Introduction to Computer Science - C++ is a
first year computer science course designed to teach the basic concepts
of computer science and Object Oriented Programming." I hope the other
"basic concepts" come though a little clearer!

Brian Harvey

2006-01-19, 7:07 pm

"H." <hbe123@gmail.com> writes:
>The

part is that this isn't just a programmer; it's a teacher!

You should send him an email.

Ulrich Hobelmann

2006-01-19, 7:07 pm

Brian Harvey wrote:
> "H." <hbe123@gmail.com> writes:
>
> You should send him an email.

I don't know if this applies to teachers (they usually have a better
understanding, otherwise they wouldn't have turned teacher), but in my
experience it takes very long to clean up peoples' (fellow students,
that is) misunderstandings in computer science. This is the biggest
reason why first-years shouldn't learn Java or C++; by not studying
individual features (like semantic subtyping, syntactic inheritance) but
weirdly mixed packages of them, many CS people seem to get really

. Plus it's hard to argue with them (to convince them), because
they often obstinately insist on their wrong opinion nonetheless.

So when one asks me, I try to help, but when somebody does totally

and wrong programming, I decide it's not worth the incredible
amount of time it would take.

--
The problems of the real world are primarily those you are left with
when you refuse to apply their effective solutions.
Edsger W. Dijkstra

Sponsored Links