RECURSION IN PYTHON

Recursion is defined as the process in which a function calls itself as a subroutine. The same function is called repeatedly by itself until the stopping condition is met. Recursion in python is taken as an efficient method of coding since we require very less code to write a complete program. The disadvantage of recursion is that it increases the complexity of the program and is harder to debug.

The stopping condition of recursion in python are:

1. 1. Solution has been found
2. 2. When the base case is met. The base case is the condition in which the problem can be solved without recursion.
3. 3. A maximum level of recursion is reached.

The recursive function will continue to call itself until some stopping (base) condition is met to stop the recursion in python.

>>> def add_natural(x):
        if (x==1):
            return 1
        return (x+add_natural(x-1))
>>> num = int (input("sum of how many natural numbers ?? : "))
>>> sum = add_natural(num)
>>> print ("sum is ",sum)
 
Output:
sum of how many natural numbers ?? : 5 sum is 15

In the above example, we are writing a program to print the sum of n natural number where n is taken from the user as input. Suppose n is 5. We have defined a function named add_natural where x is taken as a parameter. During function call, 5 is passed to the defined function. During the first iteration, x is 5 so the if condition is false. In return statement, it has called itself by reducing the value of x by 1. Let’s see below: 

          5 + add_natural(4)          : First iteration

           4 + add_natural(3)         : Second iteration

            3 + add_natural(2)         : Third iteration

           2 + add_natural(2)         : Fourth iteration

           1                                       : (stopping condition met)

Hence (5+4+3+2+1) i.e 15 is returned

BENEFITS OF RECURSION

• 1. Reduces unnecessary calling of function as it calls itself until stopping condition is met
• 2. Reduces the size of code as big and complex iterative solutions become easy and simple with Python recursion
• 3. Tends to be less error-prone as it becomes much easier to visualize
• Many problem statements are recursive in essence: the best, most concise, clear and provably correct way

Recursion is usually slower than an iterative solution as Python’s stack depth is not unlimited. It requires extra storage space as for every recursive call separate memory is allocated for the variables.

Unless we explicitly set the maximum limit of recursions, the program by default will throw a Recursion error after 1000 recursions.

EXAMPLE 01: To find factorial of a number using Recursion

>>> def fac(x):
        if (x==0):
            return 1
        return (x*fac(x-1))
>>> num = int (input("enter a  number ?? : "))
>>> out = fac(num)
>>> print ("factorial of ",num," is ",out)
 
Output:
enter a  number ?? : 1
factorial of  1  is  1

EXAMPLE 02: To find n Fibonacci number using Recursion

>>> def fib(n):
            if n == 1 :
                return 1
            elif n == 2 :
                return 1
            else:
                return (fib(n-1)+fib(n-2))           
>>> num = int(input("how many fibonacci series ?? "))
>>> c = fib(num)
>>> print (c,"is the required output")
 
Output
how many Fibonacci series ?? 6
8 is the required output