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

Re: how can I convert an iterative to a recursive summation?

Expand Messages
  • Bill James
    ... Just for fun: (* Make array of ints from a to z, inclusive. *) let ( -- ) a z = Array.init (z-a+1) (fun i - i + a) ;; let summation a b =
    Message 1 of 4 , Jul 31, 2009
      --- In ocaml_beginners@yahoogroups.com, Jaques Bertrand <bertrandjaques@...> wrote:
      >
      >
      > Hi,
      >
      > I was trying to code a function that computes a summation given a lower and an upper boundry, but for some reason, I am not able to find a recursive solution. My instincts tell me that a recursive solution would be preferred in OCaml. For example, given 1 and 5, a sum of all the integers between 1 and 5 is 15. I think the recursive step would be (n-1) or (n+1), but I keep missing the guard component.
      >
      > Thus far I came up with the iterative solution:
      >
      > let summation a b =
      > let step = ref 0 in
      > for i = a to b do
      > step := !step + i
      > done;
      > !step;;
      >
      > summation 1 5;;
      > :- int = 15 and
      > summation 3 8;;
      > :- int = 33
      >
      > let summation a b =
      > let rec sum = ref 0 in
      > if b - 1 = 0 then a
      > else sum := !sum + (b - 1);;
      > # summation 1 5;;
      > -: Error: This expression has type int but an expression was expected of type unit.
      >
      > Regards,
      >
      > bj
      >

      Just for fun:


      (* Make array of ints from a to z, inclusive. *)
      let ( -- ) a z = Array.init (z-a+1) (fun i -> i + a) ;;

      let summation a b =
      Array.fold_left (fun x y -> x+y) 0 (a -- b) ;;

      print_int (summation 1 5)
    • Yang Ye
      Hi, sum := !sum + (b - 1) is of type unit so a is inferred as unit as well. The second function evaluates as int - unit - int. the correct recursive version
      Message 2 of 4 , Aug 1, 2009
        Hi,
        sum := !sum + (b - 1) is of type unit so a is inferred as unit as well. The
        second function evaluates as
        int -> unit -> int.

        the correct recursive version is
        let sum a b = let rec sum2 x = if (x = a) then a else x + (sum2 (x-1)) in
        sum2 b ;;

        Regards,
        Yang Ye

        On Sat, Aug 1, 2009 at 2:07 AM, Bill James <w_a_x_man@...> wrote:

        >
        >
        > --- In ocaml_beginners@yahoogroups.com <ocaml_beginners%40yahoogroups.com>,
        > Jaques Bertrand <bertrandjaques@...> wrote:
        > >
        > >
        > > Hi,
        > >
        > > I was trying to code a function that computes a summation given a lower
        > and an upper boundry, but for some reason, I am not able to find a recursive
        > solution. My instincts tell me that a recursive solution would be preferred
        > in OCaml. For example, given 1 and 5, a sum of all the integers between 1
        > and 5 is 15. I think the recursive step would be (n-1) or (n+1), but I keep
        > missing the guard component.
        > >
        > > Thus far I came up with the iterative solution:
        > >
        > > let summation a b =
        > > let step = ref 0 in
        > > for i = a to b do
        > > step := !step + i
        > > done;
        > > !step;;
        > >
        > > summation 1 5;;
        > > :- int = 15 and
        > > summation 3 8;;
        > > :- int = 33
        > >
        > > let summation a b =
        > > let rec sum = ref 0 in
        > > if b - 1 = 0 then a
        > > else sum := !sum + (b - 1);;
        > > # summation 1 5;;
        > > -: Error: This expression has type int but an expression was expected of
        > type unit.
        > >
        > > Regards,
        > >
        > > bj
        > >
        >
        > Just for fun:
        >
        > (* Make array of ints from a to z, inclusive. *)
        > let ( -- ) a z = Array.init (z-a+1) (fun i -> i + a) ;;
        >
        > let summation a b =
        > Array.fold_left (fun x y -> x+y) 0 (a -- b) ;;
        >
        > print_int (summation 1 5)
        >
        >
        >



        --
        Regards,
        Yang Ye


        [Non-text portions of this message have been removed]
      Your message has been successfully submitted and would be delivered to recipients shortly.