recursionfunctional-programmingocaml# trace a nested recursion in Ocaml

I am trying to understand deeply nested recursion in OCaml by using the sorting list algorithm. For this reason I am tracing the below code which has a recursive function `sort`

and calls another function `insert`

.

```
let rec sort (lst : int list) =
match lst with [] -> [] | head :: tail -> insert head (sort tail)
and insert elt lst =
match lst with
| [] -> [ elt ]
| head :: tail -> if elt <= head then elt :: lst else head :: insert elt tail
```

I understand the first recursive calls for `sort`

, but after that I cannot follow.

For instance, suppose we have the list `[6, 2, 5, 3]`

. After sorting the `tail`

of this list as `2,3,5`

where in the code the `head`

`6`

is compared to each element of this tail? Can somebody provide a hint for the trace results?

```
utop # sort [6; 2; 5; 3];;
> sort <-- [6; 2; 5; 3]
> sort <-- [2; 5; 3]
> sort <-- [5; 3]
> sort <-- [3]
> sort <-- []
> sort --> []
> insert <-- 3
> insert -->
> insert* <-- []
> insert* --> [3]
> sort --> [3]
> insert <-- 5
> insert -->
> insert* <-- [3]
> insert <-- 5
> insert -->
> insert* <-- []
> insert* --> [5]
> insert* --> [3; 5]
> sort --> [3; 5]
> insert <-- 2
> insert -->
> insert* <-- [3; 5]
> insert* --> [2; 3; 5]
> sort --> [2; 3; 5]
> insert <-- 6
> insert -->
> insert* <-- [2; 3; 5]
> insert <-- 6
> insert -->
> insert* <-- [3; 5]
> insert <-- 6
> insert -->
> insert* <-- [5]
> insert <-- 6
> insert -->
> insert* <-- []
> insert* --> [6]
> insert* --> [5; 6]
> insert* --> [3; 5; 6]
> insert* --> [2; 3; 5; 6]
> sort --> [2; 3; 5; 6]
>
> - : int list = [2; 3; 5; 6]**
```

Solution

First of all, there's no reason to have `insert`

and `sort`

being mutually recursive since `insert`

doesn't depend on `sort`

. So you could write it like this:

```
let rec insert elt lst =
match lst with
| [] -> [ elt ]
| head :: tail -> if elt <= head then elt :: lst else head :: insert elt tail
let rec sort (lst : int list) =
match lst with [] -> [] | head :: tail -> insert head (sort tail)
```

Now, what happens in `insert`

? The function tries to insert an element `elt`

in a **sorted** list with the invariant that all elements before it should be smaller and all the elements after should be higher.

Two cases happen:

- if the list is empty, the invariant is ensured if you just return a list containing the element you were trying to insert.
- if the list is not, it's composed of an element we'll call
`head`

and the rest of the list that we'll call`tail`

. Now we have two new cases:- if
`elt <= head`

then all the elements of the list are higher than`elt`

so you just return`elt :: list`

(for example if you call`insert 1 [2; 3; 4]`

you'll return`[1; 2; 3; 4]`

- otherwise,
`head < elt`

so we need to add`head`

in front of the list that will be returned by inserting`elt`

to`tail`

, hence the recursive call to`insert elt tail`

- if

Now, when you call sort you call it like this:

```
insert head (sort tail)
```

Why so? Because the invariant only works if the list you're trying to insert head into is sorted (hence the bold sorted before). So you need to sort `tail`

before inserting `head`

into it.

If you have the following list: `[3; 2; 1]`

, you'll call

`insert 3 (sort [2; 1])`

which is transformed in

`insert 3 (insert 2 (sort [1]))`

which is transformed in

`insert 3 (insert 2 (insert 1 (sort [])))`

which is resolved in

`insert 3 (insert 2 [1])`

which is resolved in

`insert 3 [1; 2]`

which is resolved in

`[1; 2; 3]`

And your list is sorted.

[EDIT]

Here's the code with some printing to see what's happening:

```
let pp_sep ppf () = Format.fprintf ppf "; "
let rec insert elt lst =
Format.printf "@[<v 2>(Insert %d in [%a]" elt
Format.(pp_print_list ~pp_sep (fun ppf d -> fprintf ppf "%d" d))
lst;
let l =
match lst with
| [] -> [ elt ]
| head :: tail ->
if elt <= head then elt :: lst
else (
Format.printf "@,";
head :: insert elt tail)
in
Format.printf ")@]";
l
let rec sort (lst : int list) =
match lst with
| [] -> []
| head :: tail ->
Format.printf "@[<v 2>(Sort [%a] then insert %d@,"
Format.(pp_print_list ~pp_sep (fun ppf d -> fprintf ppf "%d" d))
tail head;
let l = insert head (sort tail) in
Format.printf ")@]@,";
l
```

```
# sort [3;2;1];;
(Sort [2; 1] then insert 3
(Sort [1] then insert 2
(Sort [] then insert 1
(Insert 1 in []))
(Insert 2 in [1]
(Insert 2 in [])))
(Insert 3 in [1; 2]
(Insert 3 in [2]
(Insert 3 in []))))
- : int list = [1; 2; 3]
```

- How to recursively check if a String starts and ends with another String in Java without equals()?
- Optimization of tail recursion in R
- How to calculate a unit price with a recursive Tree structure in a database
- Repacking or printing unpacked Lua tables
- Recursively merge two associative 2d arrays
- Jinja templating with recursive in dict doesn't works
- Trace a recursive method
- JS - recursive function on multidimensional array to filter out only "checked" items (and its parents if a child is selected)
- Codility OddOccurrencesInArray Problem - Recursion and Python
- Check if a multidimensional array has any non-empty leaf nodes
- Is this a top down or bottom up recursion
- Convert recursion to iteration
- Space complexity for recursive calls on binary search tree
- Real-world examples of recursion
- How to obtain n-th even triangle number using recursive algorithm
- ArrayIndexOutOfBoundsException while walking 2D array recursively to solve a maze
- Is such a function structure tail recursive?
- Flatten multidimensional array 1 level php
- extract list from cell and add new rows to a df
- Fastest way to divide a 2D array in python into counterclockwise patches
- Merge two associative multidimensional arrays
- Octree implementation in Rust: why is the insert function duplicating insertions and how could I go about fixing this?
- convert binary to decimal using single linked list and recursive method in java
- How to use recursive SQL to find the parent ID
- Recursion function for counting the number of digits in a number?
- C# Dictionary recursion
- How to transform flat array to a list of hierarchical trees based on a field with a list of enums denoting the level
- How can I Create folders recursively in Delphi?
- What is the difference between divide and conquer, and branch and reduce?
- Linked-list population via recursion in C++