Learnerslesson
   JAVA   
  SPRING  
  SPRINGBOOT  
 HIBERNATE 
  HADOOP  
   HIVE   
   ALGORITHMS   
   PYTHON   
   GO   
   KOTLIN   
   C#   
   RUBY   
   C++   




PYTHON - RECURSION


'Recursion' is a technique where a Function calls itself. It might look a little tough. But we will try making it as easy as possible.


Let us understand 'Recursion' using the program to find out the Factorial of a number.


Below is how we calculate the factorial of a number.


Say, we want to calculate the factorial of 3.


3 * 2 * 1 = 6

Similarly, the factorial of 6 is,


6 * 5 * 4 * 3 * 2 * 1 = 720

Below is a program to calculate the factorial of '3' using 'Recursion'.


Example :


def fact(x):
    if x == 1:
        return 1
    else:
        return (x * fact(x-1))

n = 3
f = fact(n)
print("The factorial of", n, "is", f)


Output :



  The factorial of 3 is 6

In the above code, we are calculating the factorial of '3'.


So, we have initialised the value of 'n' with '3'.


n = 3

And called the 'fact(n)' Function, passing the value of 'n'(i.e. '3').


f = fact(n)

And the execution of 'fact' Function begins.


def fact(x):
    if x == 1:
        return 1
    else:
        return (x * fact(x-1))
    

So, the value of 'x' is '3'(That is passed as argument).


java_Collections

Then in the next line, we have checked if the value of 'x' is '1'. If so, the method execution stops and '1' is returned.


if x == 1:
    return 1
    

Now, since the value of 'x' is '3'. We come to the else part and come across the recursive call, where the 'fact' Function calls itself.


else:
    return (x * fact(x-1))
    

But the thing to note is that there is a 'return' statement. A 'return' statement actually means to 'return' the value and finish the Function execution.


But in this case the value will not be returned immediately. Instead, the 'fact' Function calls itself.


And Python, maintains an internal Stack that is hidden from the user.


So, in the return statement, if we substitute the value of 'x' with '3'.


return (x * fact(x-1))

It becomes 'return (3 * fact(2))'. And that is kept in the internal stack maintained by Python.


For 'fact(3)', Python keeps a note in stack that the return value is 'return (3 * fact(2))'.And the value of 'fact(2)' is yet to be determined.


java_Collections

Now, 'fact(2)' Function from 'return (3 * fact(2))' with the new 'Argument', '2' is called.And the first pass begins.


1st Pass


So, the value of 'x' is '2'(That is passed as recursive argument).


java_Collections

And the 'fact(2)'(i.e. After substituting the value of 'x' by '2') Function execution begins with new Argument '2'.


def fact(x):
    if x == 1:
        return 1
    else:
        return (x * fact(x-1))
    

Similarly, the control comes to the 'else' statement and the 'return' statement is encountered.


else:
    return (x * fact(x-1))
    

Even in this case Python finds a recursive call to the 'fact' Function.


So, it stores the value in the stack.


So, in the return statement, if we substitute the value of 'x' with '3'.


return (x * fact(x-1))

It is 'return (2 * fact(1))'.


java_Collections

Now, 'fact(1)' Function with the new 'Argument', '1' is called. And the second pass begins.


2nd Pass


So, the value of 'x' is '1'(That is passed as recursive argument).


java_Collections

And the 'fact(1)' Function execution begins with new Argument '1'.


def fact(x):
    if x == 1:
        return 1
    else:
        return (x * fact(x-1))
    

Now, the control comes to the 'if' statement


if x == 1:
    return 1
    

and the 'return 1' statement is encountered.


Now, Python doesn't find a recursive call to the 'fact' Function.


And the return value for 'fact(1)' is '1'.


java_Collections

And now, it is time for Python to 'Backtrack'


i.e. To get the values out of the Stack.


So Python goes to the top element of the stack and takes it out.


java_Collections

And the topmost element is 'fact(2)' with value 'return (2 * fact(1))'. So, it takes out 'fact(2)' and substitutes the value of 'fact(1)' with '1'.


And the value of 'fact(2)' becomes,


'fact(2)' --> 'return (2 * fact(1))' --> return (2*1) --> return 2

So, the value of 'fact(2)' is '2'.


java_Collections

So Python goes to the stack again.


java_Collections

And the topmost element is 'fact(3)' with value 'return (3 * fact(2))'. So, it takes out 'fact(3)' and substitutes the value of 'fact(2)' with '2'.


And the value of 'fact(3)' becomes,


'fact(3)' --> 'return (3 * fact(2))' --> return (3*2) --> return 6

So, the value of 'fact(3)' is '6'.


java_Collections

Now since, the Stack is empty,


java_Collections

Python returns the value of 'fact(3)' i.e. '6'.


And finally, the value is 'fact(3)' is returned.


f = fact(n)

And the returned value is assigned to 'f'.


java_Collections

And the print statement,


print("The factorial of", n, "is", f)

Prints the output.


The factorial of 3 is 6

Next, let us take the example of Fibonacci Series.


A Fibonacci Series is generated by by adding the previous number of the sequence with the current number to generate the next number in the sequence.


Too much in a line? Let us make in simple.


Let us see the first six numbers of the Fibonacci Series.


0  1  1  2  3  5

Click here to understand Recursion using Iteration

Let us understand Fibonacci Series using Recursion.


Example :


def fib(n):	
    if(n == 0):
        x = 0
    elif(n == 1):
        x = 1	
    else:
        x = fib(n - 1) + fib(n - 2);	
    return x;	

for i in range(6): 
    print(fib(i))


Output :



  0
  1
  1
  2
  3
  5

The explanation is left for the users to understand.