Understanding Recursion! The easy way.

Aoi — Fri, 16 Jun 2023 15:08:45 +0000

Recursion: It's like falling down a rabbit hole and realizing the rabbit hole is inside another rabbit hole, and it just keeps going

Let's make this hard topic easy for our brains. How do you add these numbers? 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = ?
You might say we simply add them together or type them out on a calculator. If you thought so you are correct but what if we wanna write it down as a function? Here comes recursion and together we will go through the simple steps to write our own unique function.

If the Math Genius within you said "Oh, can't you just use an AP?" Then we will talk about that at the end of this post.

The Simple Process

Before we begin lets name our function fn(n) where "n" is the starting number. So in theory

fn(9) = 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1

What if we reduce that n to 8. Now our function gives

fn(8) = 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1

Notice something? fn(8) contains a part of fn(9). So lets just replace that.

fn(9) = 9 + fn(8)

What about fn(8)? If you think about it

fn(8) = 8 + fn(7)

Don't you see a pattern here? In both of them, we are simply adding our number (9) to the function of number before it. So can we write that as

fn(n) = n + fn(n-1)

Here (n-1) is the number before it.

By this, we have successfully divided our problem into a smaller problem. Step 1 complete.

Finding the End

Now we know

fn(9) = 9 + fn(8)

we need to find an end to it. In our series we assumed that the ending number is always 1. So what will fn(1) be? Since our last number is one, we have to stop here. Hence

fn(1) = 1

Making it work (hopefully)

Begin.

fn(n) = {
  if ( n = 1 ){
    return 1  
  }  else {
    return n + fn(n-1)
  }
}

and that's it. We have our function. Time to run it in our heads. (I am just gonna type it out ok?)

We should take a smaller number so it's simpler. So let n be 3.

fn(3) = 3 + fn(3-1)
fn(3) = 3 + 2 + fn(1)
fn(3) = 3 + 2 + 1

So it works. (Nice) Now you know how to write recursive function which call themselves but it's always good to see the problems with any good techniques.

Problems

What is we do fn(-1). Try it yourself, did you get an output?
You won't, and that is because we never stop, our stop condition only checks if the number is 1 but we never thought of negative numbers. You might think we can just make it

fn(n) = {
  if ( n <= 1 ){  //Triggers if n is less than or equal to 1
    return 1  
  }  else {
    return n + fn(n-1)
  }
}

In our case this was a simple example, but when we try to make more complex functions, we might miss out on a rare one time end case which we never thought of. In this case our function will be stuck calling itself over the over again without stop. (Which is really bad).

Hence many companies making robust software actually avoid using recursive functions. They don't want their software to be stuck calling itself instead of collecting user data.

Most of the time there are even better ways to solve these problems without recursion. You might have studied in your school and concept of Arithmetic Progression (AP). We can use that to remake our function.

fn(n) = n * (n + 1) / 2

This is a much faster and simpler way to solve this problem.

The End