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

Expand Messages
• ... 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)
• 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.