Browse Groups

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

(4)
• NextPrevious
• ... 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
View Source
--- 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)
• 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 1 of 4 , Aug 1, 2009
View Source
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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.