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 theFactorial, How to solve it??

Before writing the code, let see what is theFactorial.

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 byn!.
So theFactorial of 4 is
4! = 4*3*2*1 = 24

So theFactorial is the multiplying of the number-n until to theone.
And the general formula ofFactorial 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? theFactorial number-n multiply until one.
More About Factorial

Let Code

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

We will write aFactorial Function namedfac() and it takes one argumentn as parameter.fac(n) computen! .
How to compute??
The formula of Factorial isn! = n*(n-1)!

So the functionfac(n) return the answer of n! computingn*(n-1)! until to one.

fac(n) = n * fac(n-1) # fac(n-1) means (n-1)!

Here is the problem!!!

This functionfac(n) doesn't execute until one. It will run forever before stack memory is full.
Becausefac(n) call itself forever even it will reachone.
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 isBase Case.

What is a actuallyBase Case.
It means that when the function recursion reachBase Case the program must stop and return the result to previous function recursion.

For our problem, theBase Case isone.

So, Here is our function definition again..

fac(n) = if n == 1           return 1         else n * fac(n-1)

Let excutefac(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 of100000.
Ohh..goddd... A Huge Number!!!!
In this case, Stack Over Flow error will rise. Because ifFactorial of 4 even takes many steps, How many steps does100000 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 declareFactorial functionfac(). But now we will take two argument as parameter, number(n) and accumulator(a). Accumulator is doing the task which takes the result ofFactorial instead of going until base case. And Accumulatora is initialize 1 at first

Let Code

fac(n,a=1) = fac(n-1,a*n)

Hey,Don't forget theBase Case. It is very curial in Recursion.

fac(n,a=1) = if n == 1             return a           else fac(n-1,n*a)

Let excutefac(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 informshowwaiyan555@gmail.com

Here is the reference