Understanding Recursion! The easy way.
Tags: tutorial, beginners, coding, interview
Published: 2023-06-16 15:08:45

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

1. fn(3) = 3 + fn(3-1)
2. fn(3) = 3 + 2 + fn(1)
3. 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
So now you know recursion, which you can use to be a better programmer _(Or impress your interviewer)_.