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.
More About 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?

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