[plt-scheme] guido on tail recursion

I suppose you'll get several answers to your questions, but I want to
try answering.

On Sat, Apr 25, 2009 at 12:32 PM, emre berat nebioğlu <beratn at gmail.com> wrote:
> this will be a newbie question.I read all mail but i wonder something.
> can we say iteration instead of tail recursion.

Shriram doesn't like the term `tail recursion' either, but `iteration' seems to
imply a sequential, one-at-a-time approach.  When I say `tail recursion', I
mean something more than just iteration.

I like the `subproblem' and `reduction' terminology.  There are two ways to
solve a complex problem:

1) break it into simpler `subproblems', solve each
subproblem, then combine the results into a solution,

2) reduce the problem to a simpler problem that has the
same answer and solve the simpler one instead.

> I dont know how to write a
> program with iteration in scheme
> in java there are for,do while but someone said you can make loop in scheme.

One important point is that you don't need to do anything special in Scheme
to get iteration.  A process in Scheme will execute iteratively if it consists
of a chain of reductions.  In languages like Java, the programmer has to
specifically instruct the computer to behave iteratively through use of special
iteration constructs like `for', `do', and `while'.  In Scheme, the computer
figures this out all by itself.

> In tail recursive, program can be written by adding one extra parameter in
> scheme,in java.But logic is same in both tail recursion and iteration "not
> using stack (memory)". I mean using temprary value instead of using
> memory.If i make a mistake i am sorry.I am beginner on programming.

I think I understand what you mean here.  It is often the case that by
adding an additional parameter you can transform a program from a
recursive one into an iterative one.  (But not always.  I think you can
only transform `primitive recursive' programs this way.)

> And why are we writing recursive program.There are some advantages on that ?

Yes.  There are recursive programs that cannot be expressed as iteration.
In fact, the set of programs that can be expressed with iteration is
much smaller than the set of programs that can be expressed with
recursion.  And it appears to be the case that if you can't express a program
recursively, then you can't compute it at all (through any means!).

So recursion is the most powerful tool we have.

> Let say we wrote factorial function with recursion and call it like
> factroail(50).Program stuck.If you use laptop,your machine warm up,may be
> other process on machine cannot be proceed for sometime.
>
> But you wrote this program with tail recursive.Your calculation ends with
> two or three second.
>
> So may be we prefer CPS.But both CPS and tail recursion is faster and
> freeofcost and not diffucult for machine.But recursive is opposite.Why do we
> still write program with recursive.

Not every problem can be transformed like this.  And even if you *can* rewrite
a program to be iterative, it may not be the clearest way of expressing what
you want.

>
> (your discussion is very advanced to me and i ask few question i try to
> improve myself i hope you are welcommed me)
>
>
> On Sat, Apr 25, 2009 at 9:49 PM, Joe Marshall <jmarshall at alum.mit.edu>
> wrote:
>>
>> The word `call' itself is problematic because it implies a return.
>>
>>
>> On Sat, Apr 25, 2009 at 11:42 AM, Shriram Krishnamurthi <sk at cs.brown.edu>
>> wrote:
>> > It is dangerous to use the term "tail recursion" ever, unless you
>> > really, really mean recursion in the very narrow sense by which the
>> > doofus-in-the-street understands it, namely "a function that
>> > *directly* calls itself".
>> >
>> > I have seen an especially strong trend amongst MIT folks to use "tail
>> > recursion" to refer to the general case of "a sequence of calls that
>> > eventually result back in the same function, even if indirectly".
>> > This is technically correct, and the meaning of this general phrase
>> > may be obvious to all members of the very highly intelligent species
>> > that populates MIT.  But it confuses the doofus, and that's a problem,
>> > because it leads to the sort of confusion in Guido's message and
>> > ensuing discussion -- on a topic that needs less, not more, confusion.
>> >
>> > [Tail calls that do not lead to recursion are still worth optimizing,
>> > but they cannot lead to order-of-complexity increases in size except
>> > in pathological cases, so they are not as interesting to focus on
>> > because that, too, distracts the conversation.]
>> >
>> > Shriram
>> >
>>
>>
>>
>> --
>> ~jrm
>> _________________________________________________
>>  For list-related administrative tasks:
>>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>
>



-- 
~jrm