Recursion : Linear recursion and Tail recursion
Tags: computerscience, programming, algorithms
Published: 2021-10-13 16:33:31

#### What is Recursion?

In term of computer science, recursion is the calling the function itself. Yes, that all. But it's not simple though.

#### *Let take an example of the real world*

Have you ever see a photo in the photo of the photo in the photo the.... so on. This is the example of recursion process.
![Recursion process](https://storage.googleapis.com/algodailyrandomassets/curriculum/recursion/cover.jpg)
Above the exapmle, It a exactly single photo in the photo of that photo. Confused???

Here is the another photo. I named this "Recursive cat". Cute Right? HAHA.
![Recursive Cat](https://recursivelyrecursive.files.wordpress.com/2015/04/cat.jpg)
The photo depict itself in the frame and In this frame the previous photo do the same task.

*So back in computer science*, Recursion is the function calling itself and doing the same things what function does. Recursion Algorithm makes the problem into the sub-problems or smaller problems and compute until the base case. 
*(What is base case?? I will show you later. Don't worry.)*

Let get into it.
##### There is two recursive process....

* Linear Recursion
* Tail Recursion

#### Linear Recursion

Linear recursion is the normal recursion and It needs to understand before going to the tail recursion. 
Let take a look a problem.

If we wanna write a function that compute the **_Factorial_**, How to solve it??

Before writing the code, let see what is the *Factorial*.

##### Factorial

In Mathematics. *Factorial* is the positive integer which is product of a number and less then it. Yes, It look like a series. *Factorial* of the number(n) is denoted by **n!**.
So the *Factorial* of 4 is 
`4! = 4*3*2*1 = 24`

So the *Factorial* is the multiplying of the number-n until to the **one**.
And the general  formula of *Factorial* is
` n! = n*(n-1)! `

Let substitute 4 in this Formula
```
4! = 4*3! # (4-1)! is 3!
     4*3*2!
     4*3*2*1! # the value of 1! is 1 so..
     4*3*2
     4*6
     24
``` 
See? the *Factorial* number-n multiply until one.
[More About Factorial](https://en.wikipedia.org/wiki/Factorial)


##### Let Code

> All of the code under is just pseudo code. I will not use any programming languages.

We will write a *Factorial* Function named ` fac() ` and it takes one argument `n` as parameter. `fac(n)` compute *n!* .
How to compute??
The formula of Factorial is ` n! = n*(n-1)! `

So the function `fac(n)` return the answer of n! computing `n*(n-1)!` until to one.
```
fac(n) = n * fac(n-1) 
# fac(n-1) means (n-1)!

```

###### Here is the problem!!!
This function `fac(n)` doesn't execute until one. It will run forever  before stack memory is full.
Because `fac(n)` call itself forever even it will reach *one*. 
When it reach one  
```
fac(1-1)
fac(0) 
fac(-1) # fac(0-1)
.........so on
```

It goes forever and when the stack memory full, it will rise an error. Also it will never give a result.And the Factorial of -1 makes non-sense.

**The Solution is _Base Case_.**

What is a actually *Base Case*.
It means that when the function recursion reach *Base Case* the program must stop and return the result to previous function recursion.

For our problem, the *Base Case* is *one*.

So, Here is our function definition again..
```
fac(n) = if n == 1
           return 1
         else n * fac(n-1)
```
Let excute `fac(4)`
```
fac(4)
= 4 * (fac(3))
= 4 * (3 * (fac(2)))
= 4 * (3 * (2 * (fac(1))) 
# So we reach the Base Case one and return the result one
= 4 * (3 * (2 * (1)))
= 4 * (3 * (2))
= 4 * (6)
= 24
```
At that time, the program will not run forever and when it reach base case, it will return 1.

That is linear recursion.

But the linear recursion has a big problem.
Yes, Efficiency.
How about if you wanna know the Factorial of *100000*.
Ohh..goddd... A Huge Number!!!!
In this case, Stack Over Flow error will rise. Because if *Factorial* of 4 even takes many steps, How many steps does *100000* takes??
```
fac(100000)
= 100000 * (fac(99999))
= 100000 * (99999 * (fac(99998)))
= 100000 * (99999 * (99998 * (fac(99997))))
# ...... so on!!!!
```
See the Problem??
The Stack memory will be full at some steps and can't call next recursion. So, stack over flow error will rise.

It will use a lot of Memory and not efficient. It will go to the base case and come back to the recursion. So, it will expand the function call stack just like above the code.

What does it look like?
![Linear Recursion Example](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2j034n0454eq60aq143w.png)
Exactly, Linear recursion looks like your workdays. On Monday, you may think "I don't need to do right now. Now I'm gonna to chill. Ok!!!". Next day, You also do the same as yesterday and next day by day. On Friday, You have a lot of things to do. It's Friday but you can't happy for weekend. 
Also Linear Recursion wait the result until it reach the base case. When you call Factorial of 100000, the computer will kick off and smash you. I'm sure.
That is the problem of Linear Recursion.

#### Tail Recursion

In Tail Recursion, Something new  happen and a  little bit change.
We also declare *Factorial* function `fac()`. But now we will take two argument as parameter, number(`n`) and accumulator(`a`). Accumulator is doing the task which takes the result of *Factorial* instead of going until base case. And Accumulator `a` is initialize 1 at first

##### Let Code
```
fac(n,a=1) = fac(n-1,a*n)
```

Hey,Don't forget the *Base Case*. It is very curial in Recursion.

```
fac(n,a=1) = if n == 1
             return a
           else fac(n-1,n*a)
```
Let excute `fac(4,a=1)`
```
fac(4,a=1)
fac(3,a=4) # a=1 and 1*4 is 4
fac(2,a=12) # a=4 and 3*4 is 12
fac(1,a=24) # a=12 and 2*12 is 24
# Here is our base case and return a which is 24
```
In Tail recursion, *Factorial* function doesn't expand the function order and efficient than the Linear Recursion.

So, I hope you have a little knowledge about recursion and recursive processes.

> All of the above are not the whole theory.It is just a knowledge sharing and a piece of tiny concept. 

**If something wrong, please inform _showwaiyan555@gmail.com_**

[Here is the reference](https://www.youtube.com/watch?v=_JtPhF8MshA&t=593s)