про кэширование рекурсивных функций:
В процессе поигранок с той же задачкой я поигрался естественно с кэшированием значений функции. Довольно очевидно, что на самом деле ее сложность n² (для кэша достаточно матрицы n×n, даже половинки), но мне стало интересно нарисовать "общее решение" - функцию, которая кэширует любую рекурсивную функцию. Получилось немножко через жопу, но забавно:

Как сделать оборачивалку функции в кэшик понятно -

let memo fn = 
   let tab = Hashtbl.create 47 in
   fun arg ->
    try Hashtbl.find tab arg with 
      Not_found -> let res = fn arg in Hashtbl.add tab arg res; res

Но у нас функция рекурсивная:

let rec count (n, m) =
      if n = m then 1
      else if n < m then 0
      else count (n - m, m) + count (n, m+1)

Понятно, что memo count работать будет - а вот кэшировать рекурсивные вызовы не будет и что в таком виде ничего не сделаешь. Надо что-то менять. Можно вспомнить, что мешающая нам рекурсия вовсе не является такой уж фундаментальной вещью и есть такая штука - Y-комбинатор, который реализует рекурсию подавая функцию ей же на вход первым параметром:

let rec y fn arg = fn (y fn) arg

Переписываем функцию в виде пригодном для его употребления:

let count count' (n, m) =
      if n = m then 1
      else if n < m then 0
      else count' (n - m, m) + count' (n, m+1)

y count n у нас считает тоже самое, что count_rec n.

Остается последний шаг - превратить Y-комбинатор в кэширующий Y-комбинатор:

let rec memo fn = 
   let tab = Hashtbl.create 1000_000 in
   let rec fn' arg =
    try Hashtbl.find tab arg with 
      Not_found -> let res = fn fn' arg in Hashtbl.add tab arg res; res
   in fn'

Ну и теперь memo count и есть то, что нам надо. Написав простенкий тестик:

let run fn n = 
    let start = Sys.time () in
    let res = fn  (n, 1) in
    printf "n=%d cnt=%d time=%f\n" n res (Sys.time () -. start); flush stdout

let _ = 
    run count_rec 110;
    run (   y count) 110;
    run (memo count) 110

Имеем на выходе:

make -k 
ocamlopt -inline 9 nums.cmxa -rectypes gil.ml -o gil
./gil
n=110 cnt=607163746 time=71.000437
n=110 cnt=607163746 time=227.194198
n=110 cnt=607163746 time=0.008001

Что можно сказать по этому поводу - оверхед от Y весьма преизрядный, от memo, понятное дело не меньше - но даже в таком лобовом исполнении ее применение более чем оправдано, а применяется оно сугубо механически.

Впрочем расписывание руками будет эффективнее, но не так поучительно.