Exception Stack_overflow for big integer in recursive functions

Question

My Quicksort code works for some values of N (size of list), but for big values (for example, N = 82031) the error returned by OCaml is:

Fatal error: exception Stack_overflow.

What am I doing wrong?
Should I create an iterative version due to the fact that OCaml does not support recursive functions for big values?

let rec append l1 l2 =
  match l1 with
    | [] -> l2
    | x::xs -> x::(append xs l2)


let rec partition p l =
  match l with
    | [] -> ([],[])
    | x::xs ->
      let (cs,bs) = partition p xs in
      if p < x then
        (cs,x::bs)
      else
        (x::cs,bs)


let rec quicksort l = 
  match l with
  | [] -> []
  | x::xs ->
      let (ys, zs) = partition x xs in
      append (quicksort ys) (x :: (quicksort zs));;

Lhooq · Accepted Answer · 2017-06-21 05:16:42Z

8

The problem is that none of your recursive functions are tail-recursive.

Tail-recursivity means that no further actions should be done by the caller (see here). In that case, there is no need to keep the environment of the caller function and the stack is not filled with environments of recursive calls. A language like OCaml can compile that in an optimal way but for this you need to provide tail-recursive functions.

For example, your first function, append :

let rec append l1 l2 =
  match l1 with
    | [] -> l2
    | x::xs -> x::(append xs l2)

As you can see, after append xs l2 has been called, the caller needs to execute x :: ... and this function end up by not being tail-recursive.

Another way of doing it in a tail-recursive way is this :

let append l1 l2 =
  let rec aux l1 l2 =
    match l1 with
      | [] -> l2
      | x::xs -> append xs (x :: l2)
  in aux (List.rev l1) l2

But, actually, you can try to use List.rev_append knowing that this function will append l1 and l2 but l1 will be reversed (List.rev_append [1;2;3] [4;5;6] gives [3;2;1;4;5;6])

Try to transform your other functions in tail-recursive ones and see what it gives you.

edited Jun 21, 2017 at 5:16

answered Jun 20, 2017 at 15:46

Lhooq

4,4611 gold badge21 silver badges39 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

ghilesZ Over a year ago

On the top of your i would add that she can also use List.partition instead of redefining her own. The partition of the stdlib is tail-recursive while her's is not

KJ7LNW · Accepted Answer · 2022-03-07 05:16:51Z

0

Best to fix the underlying problem as noted above, but if you really need a big stack, set ulimit -s. See also:

https://stackoverflow.com/a/71375559/14055985

answered Mar 7, 2022 at 5:16

KJ7LNW

1,98113 silver badges24 bronze badges

Collectives™ on Stack Overflow

Exception Stack_overflow for big integer in recursive functions

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related