## Structural and Generative Recursion

Looking at the design recipes for 2 common sorting algorithms in Scheme

Recursion is a central component in functional programming, and one of my favourity programming concepts. In this post, we are going to look at two distinct ways in which recursive functions can be designed.

We’ll using the examples of 2 very common sorting algorithms for numbers, ie, insertion sort and the quick sort. The code snippets used below have been adapted the free e-book How to Design Programs (HtDP) and translated to MIT Scheme (from a teaching language created in Racket).

This is the most common type of recursive functions that we see in functional programming languages. It follows a common template which is very similar to wishful thinking! It really intrigued me when I learnt about it back in high school and still intrigues me to this day.

“Structural” recursion uses the underlying data “structures” naturally. Here, we only ever solve a very trivial case of the problem, and then, as if by magic, recursion solves the complete problem without us telling the computer how to do it!

Let’s look at the `insertion-sort`

function that takes a list of numbers as its argument.

```
; sorts a list l in increasing order
; List-of-numbers -> List-of-numbers
(define (insertion-sort l)
(cond
((null? l) '())
(else (insert (car l) (insertion-sort (cdr l))))))
```

We have not yet defined the `insert`

function so far. This is “wishful thinking” !!
If a function `insert`

existed that would insert a given no into a sorted list at the right position, that would solve our problem! And so we just used in our recursive definition of `insertion-sort`

. Notice that all we have really just solved the trivial case of sorting an empty list. And then, we are relying on recursion to sort the entire list by just naturally traversing the data structure, ie, the list.

```
; We now define the 'insert' function from our wish list, after which our problem is solved.
; Helper function that inserts a number n into a sorted list of numbers l at its correct position
; Number List-of-numbers -> List-of-numbers
(define (insert n l)
(cond
((null? l) (cons n '()))
(else (if (<= n (first l))
(cons n l)
(cons (car l) (insert n (cdr l)))))))
; testing the insert sort function with an example
(insertion-sort '(72 45 43 29 34))
```

```
(29 34 43 45 72)
```

We see how structural recursion has a very natural design template. In generative recursion though, instead of following a simple template like we did with Insertion Sort, we need some kind of mathematical insight into the problem itself to come up with the algorithm design. For quick sort, it’s ofcourse the “divide and conquer” strategy.

```
; [List-of Number] -> [List-of Number]
; produces a sorted version of list l, assume the numbers are all distinct
(define (quick-sort l)
(cond
((null? l) '())
(else (let ((pivot (car l)))
(append (quick-sort (smallers l pivot))
(list pivot)
(quick-sort (largers l pivot)))))))
```

Here, again we used 2 functions `smallers`

and `largers`

that haven’t been defined yet, using wishful thinking once again!

```
; returns the sub list of numbers from a given list of numbers that are greater than the given number n
; [List-of Number] Number -> [List-of Number]
(define (largers alon n)
(cond
((null? alon) '())
(else (if (> (car alon) n)
(cons (car alon) (largers (cdr alon) n))
(largers (cdr alon) n)))))
; returns the sub list of numbers from a given list of numbers that are smaller than the given number n
; [List-of Number] Number -> [List-of Number]
(define (smallers alon n)
(cond
((null? alon) '())
(else (if (< (car alon) n)
(cons (car alon) (smallers (cdr alon) n))
(smallers (cdr alon) n)))))
```

Now, our function `quick-sort`

is complete, and we can test it similarly as above. Notice that the helper functions `largers`

and `smallers`

still follow the simple template of structural recursion only.

```
; testing the insert sort function with an example
(quick-sort '(72 45 43 29 34))
```

```
(29 34 43 45 72)
```

It’s generally always easier to frame a recursive function as structural recursion, rather than to wait for an “AHA” moment to design a generative recursive function. However, sometimes the extra ingenuity can be worth it. For eg., the time completexity of quick sort is `O(n * log n)`

(appending the list of `smallers`

, `pivot`

and `largers`

, which is `O(n)`

, exactly `log`

_{2}` n`

times). This is much better than our simple insertion sort function, `O(n * n)`

(the `insert`

function `O(n)`

is called `n`

times).

If you find the field of functional programming interesting, I would encourage you to check out the excellent books Structure & Interpretation of Computer Programs or SICP or HtDP. The Youtube lectures from MIT by the authors of the SICP are also a great learning resource. I’ve written a couple other blog posts on functional programming in Lisp dialects, which you might wanna check out here.

Looking at the design recipes for 2 common sorting algorithms in Scheme

Don’t teach yourself data science in 10 days, but in 10 years

Some valuable lessons I learnt in my recent job search experience

And why you don’t need another ‘How to become a data scientist in 2021’ listicle

An intuitive way to look at matrix vector multiplication, with applications in image processing

Most tech firm interviews include SQL problems for DS roles, so how should you prepare for them?

Implementing basic matrix algebra operations in Scheme using a Jupyter notebook

Building a gender classifier model based on the dialogues of characters in Hollywood movies

Simple EDA of my reading activity using tidyverse on R Markdown

My experience using productivity tools for personal projects

Comparing Tree Recursion & Tail Recursion in Scheme & Python

My notes halfway through the book Learn You A Haskell

My topsy turvy ride to data science

Books, MOOCs and other resources that I would highly recommend

The magic of SICP