Stack overflow using recursive functions in OCaml

Question

Hi, I have a little problem: I want to solve this problem with OCaml, so I tried this ->

-> let rec somme x = if ( nor (bool_of_int (x mod 3)) (bool_of_int (x mod 5))) then x + (somme x-1) else (somme x-1) ;;

val somme : int -> int = <fun>

-> somme 1000 ;;

Stack overflow during evaluation (looping recursion?).

What have I done wrong ?

---

New code I tried:

let somme2 x = if (( nor (bool_of_int (x mod 3)) (bool_of_int (x mod 5)))) then x + somme (x-1) else somme (x-1) ;;

let somme x = if x = 0 then x else somme2 x ;;

Same error.

Answer 1

I know zip about OCaml, but it looks like your code has no terminating condition for the recursion.

Answer 2

I don't really see any termination condition in the code above? Normally, I'd expect the recursion to stop for a certain value of x, possibly 0 or 1. Your code doesn't seem to include any provision like this.

Please keep in mind that I know as much about OCaml as Neil admits to.

Answer 3

1) your recusion never stops add a test like if x == 0 then 0 else ... at the beginning

2) you don't put parentheses around your x-1, so ocaml reads (somme x)-1. Write somme (x-1) instead.

Answer 4

As other have pointed out, you should include a test for the base case. You can use pattern matching:

match x with
| 0 -> ...
| n -> ...;;

Functional languages often mirror closely mathematical notation, and pattern matching actually resembles closely the way you would write the equations on paper.

Answer 5

Oh great ! It finaly worked !

I used those lines:

let rec somme x =

if x = 0 then 0 else (if (( nor (bool_of_int (x mod 3)) (bool_of_int (x mod 5)))) then x + somme (x-1) else somme (x-1)) ;;

Thank you all!

Answer 6

Here is a simple solution to the problem, maybe it will help you improve your OCaml skills

(*generates a list of the multiples of num and stops at max*)
let gen_mult num max=

  let rec gen i=

  if i*num>=max then []

  else (i*num)::gen (i+1)

  in gen 1;;

let m3=gen_mult 3 1000;;

let m5=gen_mult 5 1000;;

(*sums the multiples of 3*)
let s3=List.fold_left (fun acc x->x+acc) 0 m3;;

(*sums the multiples of 5 except those of 3*)
let s5=List.fold_left (fun acc x->if x mod 3=0 then acc else x+acc) 0 m5;;

let result=s3+s5;;

Answer 7

No terminating condition on the loop. To fix your code:

let rec somme1 x = 
  if x <= 0
    then 0
    else if ((x mod 3) = 0) or ((x mod 5) = 0)
      then x + (somme1 (x-1))
      else somme1 (x-1);;

somme1 1000;;

To improve your code, you'd make your function tail-recursive.

let rec somme2 x accum = 
  if x <= 0
    then accum
    else if ((x mod 3) = 0) or ((x mod 5) = 0)
      then somme2 (x-1) (accum+x)
      else somme2 (x-1) accum

somme2 1000 0;;

The difference between the two versions is that, in the tail-recursive case, the results of the recursive call are precisely the same as the result of the function, so no intermediate state needs to be stored to finish the calculation after the recursive function is called. When you call somme1 1000;; then, because (1000 mod 5 == 0) or (1000 mod 3 == 0) evaluates true, you get the recursive call 1000 + (somme1 999), which, to complete, requires the recursive call 999 + (somme1 998). The compiler has to keep the numbers 1000 and 999 around on the stack until somme1 finishes executing, which it doesn't (no terminating condition), so your stack fills up trying to store 1000 + (999 + (996 + (995 + ....

This will be equivalent to ((((0 + 1000) + 999) + 996) + 995) + ..., but in this case there are no intermediate values needed to work on the result of the recursive calls (that is, the return value of the recursive call is the same as the return value of the function itself), so no additional stack space is necessary. The second version works this way. If it had the same bug as the first, it would not have run out of stack, but would have just continued executing indefinitely. This is considered an improvement. :-)