Exception Stack_overflow for big integer in recursive functions

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));;

Solution

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.