## Re: "ocaml_beginners"::[] [OT]: tail-recursiveness

Expand Messages
• ... Hi. Why did you call this question OT? ;) ... From what I understand, the last line of a function must be a direct call to another function. This way,
Message 1 of 8 , Sep 3, 2002
>From: Oliver Bandel <oliver@...-berlin.de>
>
>Hello,

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

>
>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?)

From what I understand, the last line of a function must be a direct call to
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.

>
>Well, but how looks this in real code?
>And how - to compare - will non-tail-recursive
>functions for the same task will look like?

It takes a little extra work to make something tail recursive. But when it
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

>
>
>Any code examples out there to compare tail-recursive
>and non-tail-recursive code at a glance (or in detail)?
>
>TIA,
> Oliver
>

Hope that helps,

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
• Hello Ryan, ... Hmhh, because it s nit language-specific and is more an algorithmic question. [...] ... [...] ... OK, then the following is *not*
Message 2 of 8 , Sep 3, 2002
Hello Ryan,

On Tue, 3 Sep 2002, Ryan Tarpine wrote:

> >From: Oliver Bandel <oliver@...-berlin.de>
> >
> >Hello,
>
> Hi. Why did you call this question OT? ;)

Hmhh, because it's nit language-specific and is more
an algorithmic question.

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

OK,

then the following is *not* tail-recursive:

let times n s = match n with
0 -> ""
| _ -> s ^ times (n-1) s

BTW: does it mke a differnece (in any respect, maybe ocaml-specific?)
to write it in this way:

let times n s = match n with
0 -> ""
| _ -> times (n-1) s ^ s

And how could a tail-recursive version look like?

And: Is there a mathematical form to write down
the translation from any-recursion to tail-recursion?

IMHO this must be possible to write down in some
mathematical form, so that it can be applied to many
different problems (e.g. for string concatenation,
as in the example above)?

Any Hints?

Ciao,
Oliver
• ... well, this is a tail call, a tail recursion is when the tail call is recursive call. ... [...] ... one can also write : let sum n = let rec aux n acc = if
Message 3 of 8 , Sep 3, 2002
"Ryan Tarpine" <rtarpine@...> writes:

>>From: Oliver Bandel <oliver@...-berlin.de>
>>
>>Hello,
>
> Hi. Why did you call this question OT? ;)
>
>>
>>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?)
>
> From what I understand, the last line of a function must be a direct call to
> another function.

well, this is a tail call, a tail recursion is when the tail call is
recursive call.

>>Well, but how looks this in real code?
>>And how - to compare - will non-tail-recursive
>>functions for the same task will look like?
>
> It takes a little extra work to make something tail recursive. But when it
> 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 acc =
> if n = 0 then acc
> else (sum (n-1) (acc+n))
> ;;

one can also write :

let sum n =
let rec aux n acc =
if n = 0 then acc
else aux (n-1) (acc+n) in
aux n 0

Then the function sum doesn't have the acc argument. Only the local
function aux have it.

--
Rémi Vanicat
vanicat@labri.u-bordeaux.fr
http://dept-info.labri.u-bordeaux.fr/~vanicat
• ... This is just to add that as Rémi said in a previous *great* posting, most of the time one can transform a normal recursive function into a tail
Message 4 of 8 , Sep 3, 2002
Il Wednesday 04 September 2002 00:57, Ryan Tarpine ha scritto:
> * 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

This is just to add that as Rémi said in a previous *great* posting,

" most of the time one can transform a normal recursive
function into a tail recursive by :
- moving of the try with construct

Cheers
Ernesto
PS until now I didn't have any idea about the organization of memory for
computing. Now the expression "control-stack frames" inspires me plenty of
inspired inspirations. I mean, CPUs become suddenly a product of Mankind :-)
• ... An odd question: I ve often seen this nick, aux , used by French speaking programmers. Where does it come from ? I can t translate it immediately into its
Message 5 of 8 , Sep 3, 2002
Il Wednesday 04 September 2002 01:42, Remi VANICAT ha scritto:
> let sum n =
> let rec aux n acc =
> if n = 0 then acc
> else aux (n-1) (acc+n) in
> aux n 0

An odd question: I've often seen this nick, "aux", used by French speaking
programmers. Where does it come from ?
I can't translate it immediately into its signification. I think about
"augmenteur" ou "auxiliaire" but I'd like to hear from you.

Thanks
Ernesto
• ... it is auxiliaire. Dict tell me : moi@debian:~/lang/ocaml/test\$ dict auxiliary [...] 1. A helper; an assistant; a confederate in some action or enterprise.
Message 6 of 8 , Sep 3, 2002
Stalkern 2 <stalkern2@...> writes:

> Il Wednesday 04 September 2002 01:42, Remi VANICAT ha scritto:
>> let sum n =
>> let rec aux n acc =
>> if n = 0 then acc
>> else aux (n-1) (acc+n) in
>> aux n 0
>
>
> An odd question: I've often seen this nick, "aux", used by French speaking
> programmers. Where does it come from ?
> I can't translate it immediately into its signification. I think about
> "augmenteur" ou "auxiliaire" but I'd like to hear from you.

it is auxiliaire.
Dict tell me :
moi@debian:~/lang/ocaml/test\$ dict auxiliary
[...]
1. A helper; an assistant; a confederate in some action or
enterprise.
[...]
4. (Math.) A quantity introduced for the purpose of
simplifying or facilitating some operation, as in
equations or trigonometrical formul[ae]. --Math. Dict.

here it is not a quantity but a function, so it should be good in
English too (but if you have a better translation, tell me, I will try
to use it).

--
Rémi Vanicat
vanicat@labri.u-bordeaux.fr
http://dept-info.labri.u-bordeaux.fr/~vanicat
• ... Yet you won t get an important feature of OCaml if you don t know it :) Stack overflows aren t fun for anyone, plus tail recursion often makes things
Message 7 of 8 , Sep 4, 2002
>From: Oliver Bandel <oliver@...-berlin.de>
>Subject: Re: "ocaml_beginners"::[] [OT]: tail-recursiveness
>
>Hello Ryan,
>
>
>On Tue, 3 Sep 2002, Ryan Tarpine wrote:
>
> > >From: Oliver Bandel <oliver@...-berlin.de>
> > >
> > >Hello,
> >
> > Hi. Why did you call this question OT? ;)
>
>Hmhh, because it's not language-specific and is more
>an algorithmic question.

Yet you won't get an important feature of OCaml if you don't know it :)
Stack overflows aren't fun for anyone, plus tail recursion often makes
things faster, I believe

>...
>
>OK,
>
>then the following is *not* tail-recursive:
>
>
>let times n s = match n with
> 0 -> ""
> | _ -> s ^ times (n-1) s
>

Correct

>
>BTW: does it mke a differnece (in any respect, maybe ocaml-specific?)
> to write it in this way:
>
>
>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.

>
>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)
;;

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.

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.

>
>And: Is there a mathematical form to write down
>the translation from any-recursion to tail-recursion?
>
>IMHO this must be possible to write down in some
>mathematical form, so that it can be applied to many
>different problems (e.g. for string concatenation,
>as in the example above)?
>
>Any Hints?

Looking on Google quickly, I see
http://www.owlnet.rice.edu/~comp210/96spring/Labs/lab09.html
which says

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.

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 :)

>
>Ciao,
> Oliver
>

Amike,

Ryan Tarpine

_________________________________________________________________
MSN Photos is the easiest way to share and print your photos:
http://photos.msn.com/support/worldwide.aspx
• Hi, ... [...] ... [...] ... I thought, maybe language-specific things could make a difference here. ... OK. ... Yes, this is clear. ... Yes, clear. [...] ...
Message 8 of 8 , Sep 4, 2002
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
Your message has been successfully submitted and would be delivered to recipients shortly.