Recursion- A mathematical perspective [Math Monday]

Understanding the history behind recursion and how can use it to get better at recursive programming

Apr 12, 2022

Hello hello reader,

Hope your week is off to a groovy start. To make it even better, we will be covering the theory behind recursion. I know Recursion is something that scares a lot of you, so we will cover it. It can be a very comprehensive topic, so we will split it up into multiple posts. This post will help you understand the Math behind recursion. We will then cover how to get good at recursion for coding interviews in a separate post. I will then also write about Recurrence Relations, the foundation behind time and space complexity calculations. You have a lot to look forward to, so make sure you keep checking in.

Recursion is based on a very important principle in Math

The Principle of Mathematical Induction

Some of you that studied Discrete Math, or Logic, might remember this principle. I remember a lot of people struggled with this, and many others have no idea why it is important. However, once you do understand the philosophy behind PMI, you will have a deeper understanding of Recursion. So bear with me, as we make a slight detour into this important principle before I tie it into Recursion and how you can use it.

I promise, this is super duper important

Mathematical Induction is a technique for proving statements. When implementing it, all proofs follow a particular structure-

We have a base case for which we prove our statement. Proving for our base case is generally very simple. We can simply put the values into our expression
Then we assume that our statement holds true for our arbitrary number k. We can make this assumption since we know that there is at least one k (our base case), where our statement is true. This is called the inductive assumption.
We then attempt to prove our statement for the value k+1. This typically involves the expression being split into our inductive assumption and the other part. This is the inductive step.

This is an example of PMI. Take a second to review it. The process is easier than people think.

Now let’s look at the principle of PMI and why it is theoretically sound.

Why does Mathematical Induction work?

Imagine we have a statement for which our base case was b. Once we prove our statment for b, we know that the inductive assumption is true for k=b. So when we prove our statement for the next step (k+1), we have now proved the statement for b+1. By the same principle, b+1 is now our k, and the statement is true is for b+2. And so on. This is because we took arbitrary values for k and k+1.

Some of you might have noticed that PMI relies on a fundamental assumption- there has to be a minimum value in our domain, which will be our base case. Very good. This assumption is called the Well Ordering Principle. While it sounds fancy, the principle is relatively straightforward-

Don’t overlook how important this is though. Many Discrete Math Principles are somewhat obvious but are crucial to Computer Science.

We can use PMI on all sets that are Well Ordered (follow the principle). To get good at PMI, I suggest going on YouTube/Google and looking up some PMI principles. A little bit of practice in actually writing the proofs will be very helpful in improving. Since most of you are not trying to be mathematicians, you can stick to the relatively easy PMI questions. Getting used to the technique is the important bit. For really good results, try to come up with the conjectures, and base-cases yourself.

Recursion and Mathematical Induction

So what does Mathematical Induction have to do with Recursion? Let’s look at their common structures.

Reliance Base Cases- Both these techniques rely on the base case. PMI builds up the proof from the base case. Recursive problem-solving tries to reduce the problem down to the base case.

Discrete Domains- Both these techniques operate on data with discrete changes. This is explicit in PMI with Well Ordering. Recursion also needs this assumption. This is obvious with Recursive problems like Factorial which operate on integers. But even recursive data structures like LinkedLists and Graphs are discrete. A LinkedList node is often defined as

LinkedList n= (Node,Next)
Next= Node| None (this is notation representing that Next can either be a node or none)

Reduction to proved statements- Both techniques operate by reducing the conjecture into the already proven statements. Recursion does so by trying to get to base cases. PMI does so in the inductive step.

When we look at the relationship between these ideas from a theoretical perspective, something becomes clear- PMI and recursion are like mirror images of each other. Solving problems through either technique requires similar kinds of problem-solving. It is not a coincidence that Recursion came out of Math, and Indutive DataTypes were some of the earliest representations of Recursive Data Structures.

Thus, if you want to get good at Recursion, exposing yourself to PMI is a must. Most people that learn these ideas unfortunately never learn the connection between these ideas. These are complementary ideas, so learning one will naturally improve your ability to tackle another. Therefore, to develop your recursion skills, practice some PMI questions. Once you are comfortable with the Algebraic ones (some other PMIs require knowledge of advanced math), you will see your results skyrocket. At most, this process will take 3 hours. So go out and there, and do some PMI questions, and be very cognizant of the steps you take.

In the comments below, share what topic you want to focus on. I’d be interested in learning and will cover them. To learn more about the newsletter, check our detailed About Page + FAQs

If you liked this post, make sure you fill out this survey. It’s anonymous and will take 2 minutes of your time. It will help me understand you better, allowing for better content.

https://forms.gle/XfTXSjnC8W2wR9qT9

Happy Prep. I’ll see you at your dream job.

PMI is my fav kind of proof,

Devansh <3

To make sure you get the most out of Math Mondays, make sure you’re checking in the rest of the days as well. Leverage all the techniques I have discovered through my successful tutoring to easily succeed in your interviews and save your time and energy by joining the premium subscribers down below. Get a discount (for a whole year) using the button below

Get 20% off for 1 year