Your Web News in One Place

Search Archive

View All Sources

## Help Webnuz October 13, 2021 04:33 pm GMT

# Recursion : Linear recursion and Tail recursion

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

##### 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? 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 4fac(2,a=12) # a=4 and 3*4 is 12fac(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 [email protected]

Here is the reference An online community for sharing and discovering great ideas, having debates, and making friends