Loading ...
Sorry, an error occurred while loading the content.
 

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

Expand Messages
  • Ryan Tarpine
    ... 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? ;)

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

      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
    • Oliver Bandel
      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
      • Remi VANICAT
        ... 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? ;)
          >
          >>
          >>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?)
          >
          > 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
        • Stalkern 2
          ... 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
            - adding an accumulator parameter."

            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 :-)
          • Stalkern 2
            ... 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
            • Remi VANICAT
              ... 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
              • Ryan Tarpine
                ... 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
                • Oliver Bandel
                  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.