RECURSION IN PYTHON

machine learning from scratch

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

Recommended Posts

About Diwas Pandey

Highly motivated, strong drive with excellent interpersonal, communication, and team-building skills. Motivated to learn, grow and excel in Data Science, Artificial Intelligence, SEO & Digital Marketing

View all posts by Diwas Pandey →

4 Comments on “RECURSION IN PYTHON”

  1. Pretty section of content. I just stumbled upon your website and in accession capital to assert that I acquire actually enjoyed account
    your blog posts. Anyway I’ll be subscribing to your
    feeds and even I achievement you access
    consistently fast. adreamoftrains web hosting providers

  2. Howdy! Someone in my Facebook group shared this site with us so
    I came to give it a look. I’m definitely enjoying the information. I’m bookmarking and
    will be tweeting this to my followers! Fantastic blog and wonderful design and style.

Leave a Reply

Your email address will not be published. Required fields are marked *