>From: Oliver Bandel <oliver@...-berlin.de>

Hi. Why did you call this question OT? ;)

>

>Hello,

>

From what I understand, the last line of a function must be a direct call to

>I often read about tail-recursiveness, and I know

>a littlebid about it, e.g. that tail-recursiveness

>mean, that a function that returns in the last recursion

>(in the tail) does not call any functions and only

>gives back a value (?!). (correct?)

another function. This way, instead of calling the function in the last

line and returning its value, the program can just jump (like a goto in

BASIC or C) instead. It can jump because it knows that nothing else needs

to be done after than last function is called.

>

It takes a little extra work to make something tail recursive. But when it

>Well, but how looks this in real code?

>And how - to compare - will non-tail-recursive

>functions for the same task will look like?

clicks in your mind, it's very simple.

My favorite example is the function that sums all the numbers from 1 through

n:

let rec sum n =

if n = 0 then 0

else n + (sum (n-1))

;;

Tracing an example call, we get

sum 3

3 + (sum 2)

3 + (2 + (sum 1))

3 + (2 + (1 + (sum 0)))

3 + (2 + (1 + 0))

3 + (2 + 1)

3 + 3

6

It's simple, it's recursive, but it's not tail recursive. Why? In this

case, (sum (n-1)) needs to be computed, and *then* n has to added to it.

So, the program needs to remember n and come back later to add it.

A tail recursive version adds an "accumulator":

let rec sum n acc =

if n = 0 then acc

else (sum (n-1) (acc+n))

;;

Now instead of calling (sum n), though, you need to call (sum n 0). Tracing

it, we get

sum 3 0

sum 2 (0+3 = 3)

sum 1 (3+2 = 5)

sum 0 (5+1 = 6)

6

* The tail-recursive version does some work FIRST and then calls a function

with those results

* The non-tail-recursive version calls a function and then does some work

LATER with what that returned

>

Hope that helps,

>

>Any code examples out there to compare tail-recursive

>and non-tail-recursive code at a glance (or in detail)?

>

>TIA,

> Oliver

>

Ryan Tarpine, rtarpine@...

"To err is human, to compute divine. Trust your computer but not its

programmer."

- Morris Kingston

_________________________________________________________________

Chat with friends online, try MSN Messenger: http://messenger.msn.com- Hi,

On Wed, 4 Sep 2002, Ryan Tarpine wrote:

> >From: Oliver Bandel <oliver@...-berlin.de>

> >Subject: Re: "ocaml_beginners"::[] [OT]: tail-recursiveness

[...]

> >On Tue, 3 Sep 2002, Ryan Tarpine wrote:

> >

> > > >From: Oliver Bandel <oliver@...-berlin.de>

[...]

> >let times n s = match n with

> > 0 -> ""

> > | _ -> times (n-1) s ^ s

> >

> >

>

> It makes no difference, you are still joining (times (n-1) s) after it

> returns to s, only changing whether you prepend or append s. Since you are

> doing *anything* with the value after the last function returns, it cannot

> be tail recursive.

I thought, maybe language-specific things could make a difference here.

>

> >

> >And how could a tail-recursive version look like?

>

> Add an accumulator to keep track of the string made so far:

>

> let rec times n s acc = match n with

> | 0 -> acc

> | _ -> times (n-1) s (acc^s)

> ;;

OK.

>

> But this must be called as (times how_many the_string "") to work since the

> accumulator needs to start empty. We can write an auxiliary function, like

> Rémi Vanicat said, to get rid of the need for remembering the accumulator.

Yes, this is clear.

>

> let times n s

> let rec aux n acc = match n with

> | 0 -> acc

> | _ -> aux (n-1) s (acc^s)

> in aux n ""

> ;;

>

> The aux function does all the real work, times just calls it with an empty

> accumulator for you.

Yes, clear.

[...]

> >Any Hints?

>

> Looking on Google quickly, I see

> http://www.owlnet.rice.edu/~comp210/96spring/Labs/lab09.html

> which says

Ok.

>

> You can automatically convert an ordinary recursive function into a

> tail-recursive one by following these steps:

> 1. Turn the original function into a local helper function.

> 2. Add an accumulator argument to the helper function.

> 3. Change the helper function's recursive call into a tail-recursive

> call; be sure to update the accumulator appropriately.

> 4. Make the body of the main function just a call to the helper, with

> appropriate initial values.

Yes, that is a good cooking recipe.

This and the "real world examples", which were given

here, clears a lot.

>

> You can read the page, but it is written for Scheme. Most helpful pages

> seem to be for Scheme people! I would say it's a good idea to learn Scheme

> sometime :)

Yes, I have started functional programming with scheme.

And I remember the things with the accumulator. They were

written in the book about Computer Languages (Steel & Steel

I think). But a) I didn't read it complete and b) I was

a littlebid confused about thjis accumulator-stuff.

It was unclear to me, if this really was the tail-recursion.

(They (IMHO) didn't mentioned it in the (section-/chapter-title/-text);

they mentioned it somwhere in the text (so they could make it clearer,

I think.))

After browsing through Haskell- and OCaml-programming

scheme got more and more uninteresting. ;-)

Scheme maybe is good for embedded FPL-programming,

but I like Ocaml very. :) And If I have a PC/workstation,

I would prefer OCaml, because there are no problems

with memory-size and such...

Ciao,

Oliver