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

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