## Re: "ocaml_beginners"::[] Re: how can I convert an iterative to a recursive summation?

Expand Messages
• Many thanks for the suggestion. I did see however that recursion is a mixed blessing, comparing the iterative and the recursive versions. Is there any way to
Message 1 of 4 , Aug 9, 2009
Many thanks for the suggestion. I did see however that recursion is a mixed blessing, comparing the iterative and the recursive versions. Is there any way to predict or circumvent a stack overflow in this case?

let summation a b =
let rec sum x =
if (x = a) then a
else x + (sum (x - 1)) in
sum b;;

versus

let i_summation a b =
let step = ref 0 in
for i = a to b do
step := !step + i
done;
!step;;

when calculating summation 1 1000000
-: Stack overflow during evaluation (looping recursion?).
but i_summation 1 1000000
-: int = 363189984

I was *hoping* the stack overflow would coincide with exceeding the value of int 2^^31. Are we safe in believing the value int = 363189984 to be correct then? Do we need to add another statement in the recursive version that if b > 262,000 then print_string "Cannot proceed with this value, stack overflow may result!" else compute_the_value &etc. Something along the lines

let summation a b =
let rec sum x =
if (x = a) then a
else x + (sum (x - 1)) in
if not (b >= 262000) then sum b else print_string "Not possible";;

Avec de sincères amitiés

bj

--- En date de : Sam 1.8.09, Yang Ye <leafyoung@...> a écrit :

De: Yang Ye <leafyoung@...>
Objet: Re: "ocaml_beginners"::[] Re: how can I convert an iterative to a recursive summation?
À: ocaml_beginners@yahoogroups.com
Date: Samedi 1 Août 2009, 12h56

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@yahoo. com> 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]
• ... You need to read up on tail calls and tail call elimination or tail call optimization (TCO) or proper tail recursion. Essentially, you should rewrite your
Message 2 of 4 , Aug 9, 2009
On Sunday 09 August 2009 15:34:02 Jaques Bertrand wrote:
> Many thanks for the suggestion. I did see however that recursion is a
> mixed blessing, comparing the iterative and the recursive versions. Is
> there any way to predict or circumvent a stack overflow in this case?
>
> let summation a b =
> let rec sum x =
> if (x = a) then a
> else x + (sum (x - 1)) in
> sum b;;
>
> versus
>
> let i_summation a b =
> let step = ref 0 in
> for i = a to b do
> step := !step + i
> done;
> !step;;
>
> when calculating summation 1 1000000
> -: Stack overflow during evaluation (looping recursion?).
> but i_summation 1 1000000
> -: int = 363189984

You need to read up on tail calls and tail call elimination or tail call
optimization (TCO) or proper tail recursion.

Essentially, you should rewrite your code such that the recursive calls are in
tail position to ensure that stack consumption is bounded.

In this case, use an accumulator:

# let rec sum ?(t=0) a b =
if a=b then t+a else
sum ~t:(t+a) (a+1) b;;
val sum : ?t:int -> int -> int -> int = <fun>

# sum 1 1000000;;
- : int = -363189984

> I was *hoping* the stack overflow would coincide with exceeding the value
> of int 2^^31.

No. The stack is much smaller than that and the number of non-tail calls that
can be made before you run out of stack is also a function of the size of
each stack frame.

> Are we safe in believing the value int = 363189984 to be
> correct then?

Depends what you mean by "correct". I suspect it is not the answer you were
hoping for.

> Do we need to add another statement in the recursive version
> that if b > 262,000 then print_string "Cannot proceed with this value,
> stack overflow may result!" else compute_the_value &etc. Something along
> the lines
>
> let summation a b =
> let rec sum x =
> if (x = a) then a
> else x + (sum (x - 1)) in
> if not (b >= 262000) then sum b else print_string "Not possible";;

No, that is a really bad idea. You do not know when a stack overflow will
occur but can safely assume that 1,000 non-tail recursions will work.
Therefore, you can use constant or O(log n) for machine-precision "n"
non-tail recursions.

--
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e
• Hi,Would you be so kind and elaborate on the use of optional parameter to create an accumulator in the syntax let rec sum ?( t = 0 ) a b =    if a = b then t
Message 3 of 4 , Aug 9, 2009
Hi,Would you be so kind and elaborate on the use of optional parameter to create an accumulator in the syntax
let rec sum ?( t = 0 ) a b =
if a = b then t + a
else
sum ~t:( t + a ) ( a + 1 ) b;;
Although we do not get a stack overflow, the negative sign in the result does give a hint that something is amiss. For example,sum 1 1000000 (* million *)-: int = -363189984whereassum 1 1000000000 (* billion *)(* after 2-3 min pause *)-: int = -243309312but it could not possibly be smaller than the first value and I suspect we do not see all the digits in the answer inspite of the fact we do not get an overflow error.Even an iterative solution fails us, for this we need big_int and we cannot count the stars in our galaxy using a summation.With kindest regards,bj

--- En date de : Dim 9.8.09, Jon Harrop <jon@...> a écrit :

De: Jon Harrop <jon@...>
Objet: Re: "ocaml_beginners"::[] Re: how can I convert an iterative to a recursive summation?
À: ocaml_beginners@yahoogroups.com
Date: Dimanche 9 Août 2009, 16h13

On Sunday 09 August 2009 15:34:02 Jaques Bertrand wrote:

> Many thanks for the suggestion. I did see however that recursion is a

> mixed blessing, comparing the iterative and the recursive versions. Is

> there any way to predict or circumvent a stack overflow in this case?

>

> let summation a b =

> let rec sum x =

> if (x = a) then a

> else x + (sum (x - 1)) in

> sum b;;

>

> versus

>

> let i_summation a b =

> let step = ref 0 in

> for i = a to b do

> step := !step + i

> done;

> !step;;

>

> when calculating summation 1 1000000

> -: Stack overflow during evaluation (looping recursion?).

> but i_summation 1 1000000

> -: int = 363189984

You need to read up on tail calls and tail call elimination or tail call

optimization (TCO) or proper tail recursion.

Essentially, you should rewrite your code such that the recursive calls are in

tail position to ensure that stack consumption is bounded.

In this case, use an accumulator:

# let rec sum ?(t=0) a b =

if a=b then t+a else

sum ~t:(t+a) (a+1) b;;

val sum : ?t:int -> int -> int -> int = <fun>

# sum 1 1000000;;

- : int = -363189984

> I was *hoping* the stack overflow would coincide with exceeding the value

> of int 2^^31.

No. The stack is much smaller than that and the number of non-tail calls that

can be made before you run out of stack is also a function of the size of

each stack frame.

> Are we safe in believing the value int = 363189984 to be

> correct then?

Depends what you mean by "correct". I suspect it is not the answer you were

hoping for.

> Do we need to add another statement in the recursive version

> that if b > 262,000 then print_string "Cannot proceed with this value,

> stack overflow may result!" else compute_the_ value &etc. Something along

> the lines

>

> let summation a b =

> let rec sum x =

> if (x = a) then a

> else x + (sum (x - 1)) in

> if not (b >= 262000) then sum b else print_string "Not possible";;

No, that is a really bad idea. You do not know when a stack overflow will

occur but can safely assume that 1,000 non-tail recursions will work.

Therefore, you can use constant or O(log n) for machine-precision "n"

non-tail recursions.

--

Dr Jon Harrop, Flying Frog Consultancy Ltd.

http://www.ffconsul tancy.com/ ?e

[Non-text portions of this message have been removed]
• ... Sure. The optional parameter for the accumulator t is introduced with the ? (t=...) syntax, giving it a name t and a default value. When the optional
Message 4 of 4 , Aug 9, 2009
On Monday 10 August 2009 00:50:26 Jaques Bertrand wrote:
> Hi,Would you be so kind and elaborate on the use of optional parameter to
> create an accumulator in the syntax
> let rec sum ?( t = 0 ) a b =
>   if a = b then t + a
>   else
>   sum ~t:( t + a ) ( a + 1 ) b;;

Sure. The optional parameter for the accumulator "t" is introduced with the ?
(t=...) syntax, giving it a name "t" and a default value. When the optional
argument is not given via an explicit it assumes the default value of zero,
e.g. in the external call to "sum". The internal recursive call explicitly
declares the first argument with the label "t" using the ~t: syntax.

In this case, I call the style an "implicit accumulator design pattern".

Optional arguments offer an elegant solution to many practical problems and
were described in detail in the "Labeled and Optional arguments" article
(April 2008) of the OCaml Journal:

http://ocamlnews.blogspot.com/2008/04/labeled-and-optional-arguments.html

--
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e
Your message has been successfully submitted and would be delivered to recipients shortly.