# Structural and Generative Recursion

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

### Insertion Sort and Structural Recursion

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

### Quick Sort and Generative Recursion

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.

## Book recommendations from my Covid reading list

5 books to offer a different perspctive on life

## Is Data Structures & Algorithms important for a data scientist

Why do many companies still ask CS puzzle type questions in their coding round for DS roles

## Structural and Generative Recursion

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

## You are never going to be an expert in data science

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

## Tips and Tricks that helped me find a new job

Some valuable lessons I learnt in my recent job search experience

## A lookback at what I was studying as a beginner data scientist

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

## How matrices transform space

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

## How much should one know in SQL for data science

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

## Matrix algebra operations using recursion

Implementing basic matrix algebra operations in Scheme using a Jupyter notebook

## Analyzing gender bias in movie dialogues

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

## Laziness vs The Trap of Productivity & Ambition

My experience using productivity tools for personal projects

## Tree vs Tail Recursion & Memoization

Comparing Tree Recursion & Tail Recursion in Scheme & Python

My notes halfway through the book Learn You A Haskell

## How I ended up with a data science job

My topsy turvy ride to data science