Recursion

In python it is possible a function to call it self, this is called recursion .It is mostly used to solve complex problems, that can be broken down into smaller, identical problems. it seems a bit weird concept to understand,But it is not as it sounds. let me show you one clever example which could be easy way to get used to recursion.

Factorial notation would be best example for recursion. what does factorial notation even mean ?
If we say, 6!, which is read as 6 factorial, it shows the product of numbers from 1 to 6. if you take any number, lets say n, and if you say I want to calculate the n! (n factorial) , in other word you are saying  that I want to calculate 1x2x3x4...(n-2)x(n-1)xn . it is pretty straight forward, eh ?
 Note : the factorial of 0 ( 0!) is 1. 

You can write a python code which calculate the factorial of any number. there may be several ways to tackle this problem,but the best and clever way would be recursion. with out further ado lets see what the code looks like.

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

The above code shows a function which calculates factorial.  it takes n as a a parameter. n is the number that we want to calculate its factorial.
the first condition is called the base case. it checks if the value of n is 0 and if the condition happens to be True, then it returns 1. In recursion you need a base case in order to prevent infinite loop. otherwise, your code will continue executing forever. But in my factorial  function I check if the value of n is 0, which happens at some time of the loop.



As you see in the figure , I calculate the factorial of 3. first I check if 3==0, since 3 is different from 0, it execute the code in the else statement. once it  gets in to the else statement. it will get the line return n * factorial(n - 1),this line return product of 3,the current value of n, and factorial(2). here, I call the function factorial, but in this time value of n is  one less from the previous this means n is 2 now.  then the function factorial(2) begin to execute, it checks if 2==0 is True, since it is false , it gets in to the else statement then it returns 2*factorial(1,)then the function call factorial(1) go through  the same stapes,but this time it returns 1*factorial(0). now the value of n is 0 , so the base case become True, then the code in the if statement will run for the first time and it returns one.
Finally when everything get evaluated , the function returns 6, which is the product of 3*2*1

As you saw in the previous example , recursion is not as difficult as it sounds. once you get used to the concept ,you could use it to solve several problems. In short, it is clever way to approach problems.

However, most likely whatever solved with recursion can be done with loop - either while or for loop. and loops are more efficient than recursive. recursive uses more memory than for loop. so why you bother learning recursion ? when we come to complex problems,however, recursion become more handy ,easier and simpler.