Learning OCaml has made me much more comfortable dealing with recursive functions. I thought I had a good grasp of them until recently.

I’ve been going through the 99 OCaml problems, available here: Exercises

And found exercise **26 - Generate the combinations of K distinct objects chosen from the N elements of a list.** quite challenging actually.

After failing many times and giving it a few days, I realized I wasn’t making any significant progress so I peeked at the proposed solution for inspiration.

Side note, as I explored I also found that Haskell’s list comprehension feature could help, but in a static way so not quite satisfying.

```
ghci> [ (i,j) | i <- [1..4], j <- [i..4], i /= j ]
[(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]
ghci> [ (i,j,k) | i <- [1..4], j <- [i..4], k <- [j..4], i /= j && j /= k ]
[(1,2,3),(1,2,4),(1,3,4),(2,3,4)]
```

This is what I came up with (I can only encourage you to give it a go before taking a look). Assume there may be spoilers after this opening post.

```
let extract n lst =
let rec aux acc rest n =
if n = 0 then
[ List.rev acc ]
else
match rest with
| [] -> []
| x :: xs -> aux (x :: acc) xs (n - 1) @ aux acc xs n
in
aux [] lst n
;;
```

I wasn’t too pleased with the list append + the fact that the function didn’t look tail call optimized so I kept working on it and got this for a v2:

```
let extract n lst =
let () = if n <= 0 then raise @@ Invalid_argument "n must be positive" in
(* outer = [inner, inner, inner, ...] *)
let rec aux n lst (inner : 'a list) (outer : 'a list list) : 'list list =
if n = 0 then
List.rev inner :: outer
else
match lst with
| [] -> outer
| x :: xs ->
let new_outer = aux (n - 1) xs (x :: inner) outer in
aux n xs inner new_outer
in
aux n lst [] [] |> List.rev
```

So far so good? Well not quite. I don’t know what it is about this exercise but I have a mental block on it. I feel that I haven’t really developed a complete understanding of it. If I were to give it a go again in a few weeks, I’d probably struggle with it just as much.

This is in contrast with simpler recursive problems, whereas I had an epiphany and internalized the solution.

I explored various ideas, such as trying to analyze the problem with fancy tools (not OCaml related), or simply typing out the steps of execution but then I kinda loose track and I’m back at square 1.

```
-(aux [] ['A','B','C','D'] 3)-
-@-
-aux (['A']) ['B','C','D'] 2-
-@-
-aux (['B','A']) ['C','D'] 1-
-@-
-aux (['C', 'B','A']) ['D'] 0-
-@-
-['A','B','C']- oops, I'm starting to loose track here
-aux (['C', 'B','A']) ['D'] 1-
-aux (['B','A']) ['D'] 1-
-aux (['A']) ['C','D'] 2-
-aux [] ['B','C','D'] 3-
```

I also tried to print values but that didn’t help much, I guess it’s because the relation of the log messages, the expansion of the tree, and the final product isn’t very clear to me.

So, do you have any tips? What do you do when you have a mental block like that? I mean, specifically related to recursion.