Methods and Functions

Python Recursion (Recursive Function)

In this article, you will be learning how to create a recursion python (recursive function), what are its advantages and disadvantages along with examples for each.

What is Recursion?

Recursion is the process in which the function calls itself, the call may be direct or indirect. Using recursion, certain problems like Towers of Hanoi, DFS of graphs etc can be solved easily.

The most well known physical world example of recursion is infinite images formed by two parallel mirrors. The image formed acts as an object and form a new image this way the process is defined in terms of itself and hence shows recursion.

Python Recursive Function

Any function which calls itself directly or indirectly is called a python recursive function.

Example: In the recursive_function() below, the function is calling itself inside its definition.

                    

def recursive_function():

# base condition and rest of the code

# recursive call

recursive_function()

Example: A Fibonacci sequence is an integer sequence that goes like 0, 1, 1, 2, 3, 5, 8…

Let’s write a recursive code to find the Fibonacci sequence for n terms.

Code

                    

# Code to print the Fibonacci sequence up to n terms

# Recursive Fibonacci function

def recursive_fibonacci(n):

if n <= 1:

return n

else:

return(recursive_fibonacci(n-1) + recursive_fibonacci(n-2))

n_terms = 8

# check if the number of terms is valid

if n_terms <= 0:

print(“Invalid input ! Input must be a positive value”)

else:

print(“Fibonacci series is :”)

for i in range(n_terms):

print(recursive_fibonacci(i))

Output

Fibonacci series is :

0

1

1

2

3

5

8

13

Explanation

In the above example, we are calling the function recursive_fibonacci with a positive integer and it is recursively calling itself by breaking the problem into subproblems.

Like when we are finding the 5th term of Fibonacci series that is n=4, here is what happened:

                    

recursive_fibonaci(4) #first call will be made with n=4

recursive_fibonaci(3) + recursive_fibonaci(2) # second call will be made with n=3 and n=2

[recursive_fibonaci(2)+recursive_fibonaci(1)]+[recursive_fibonaci(1)+recursive_fibonaci(0)]

[recursive_fibonaci(2) + 1] + [1 + 0] # as we return n for n<=1

[recursive_fibonaci(1)+recursive_fibonaci(0)+1] +[1]

[1 + 0 + 1] + [1]

2 + 1

3

Hence the 5th term of the fibonacci series is 3.

One thing to observe from the example above is that our recursion ends when the number is 1 or less than 1. This is called the base condition of recursion, where our function stops calling itself. If there is no base condition then our recursive function will run infinite times and hence will cross the limits of depths of recursion resulting in stack overflows. If the limit of recursion depth is crossed, that is 1000 by default, it results in RecursionError.

Example:

                    

def infinite_recursion():

infinite_recursion()

infinite_recursion()

Output

Traceback (most recent call last):

File “program.pys3”, line 3, in <module>

infinite_recursion()

File “program.pys3”, line 2, in infinite_recursion

infinite_recursion()

File “program.pys3”, line 2, in infinite_recursion

infinite_recursion()

File “program.pys3”, line 2, in infinite_recursion

infinite_recursion()

[Previous line repeated 996 more times]

RecursionError: maximum recursion depth exceeded

Advantages of Recursion

The advantages of recursion are as follows:

  1. Using recursive functions helps to make code look clean, simple and elegant.
  2. Sequence creation becomes simpler and easier with recursion than using nested iterations.
  3. We can split down a complicated complex task into simpler and smaller sub-tasks using recursion.

Disadvantages of Recursion

The disadvantages of recursion are as follows:

  1. A recursive call that is a function calling itself multiple times takes a lot of time and memory which makes it inefficient and expensive.
  2. Sometimes the reasoning and the logic behind the recursion is tough to click.
  3. In case your code fails due to some small typo or logical error, it is very challenging to debug the recursive codes.

Frequently Asked Questions

Q.1. What is recursion in Python explain with example?

Answer: Recursion is the process in which the function calls itself, the call may be direct or indirect. Using recursion, certain problems like Towers of Hanoi, DFS of graphs etc can be solved easily.

The most well known physical world example of recursion is infinite images formed by two parallel mirrors. The image formed acts as an object and form a new image this way the process is defined in terms of itself and hence shows recursion.

Q.2. How does recursion work in Python?

Answer: When we call a function in python, a new local namespace is created by the interpreter. In recursion multiple instances of the same recursive function are running concurrently therefore for the function to have finite calls there is a base condition for every recursive function and that is the terminating condition where our function stops calling itself. This way in recursion we first break our problems to simpler subproblems until it reaches the base condition and concludes our answer by solving step by step from simpler to the main problem.

Q.3. Is recursion bad in Python?

Answer: Recursion can be considered bad in python because a recursive solution is generally slower than the iterative solution and also python’s stack depth is not unlimited so there are huge chances of stack overflow.

Although there are some advantages of recursion too, it helps to make code look clean, simple and elegant and problems involving sequence creation becomes simpler and easier with recursion than using nested iterations.

Q.4. What is recursion with an example?

Answer: Recursion is the process in which the function calls itself, the call may be direct or indirect. Using recursion, certain problems like Towers of Hanoi, DFS of graphs etc can be solved easily.

Example: A factorial of a number n is defined by n! where n! = 1*2*3*…*n

Let’s write a recursive code to find factorial of a number n

Code

                    

# Code to print the Factorial of a number n

# Recursive factorial function

def recursive_factorial(n):

if n <= 1:

return 1

else:

return( n*recursive_factorial(n-1) )

n = 5

# check if the number of terms is valid

if n_terms <= 0:

print(“Invalid input ! Input must be a positive value”)

else:

print(“Factorial of given number is :”)

print(recursive_factorial(n))

Output

Factorial of the given number is :

120

Share with friends

Customize your course in 30 seconds

Which class are you in?
5th
6th
7th
8th
9th
10th
11th
12th
Get ready for all-new Live Classes!
Now learn Live with India's best teachers. Join courses with the best schedule and enjoy fun and interactive classes.
tutor
tutor
Ashhar Firdausi
IIT Roorkee
Biology
tutor
tutor
Dr. Nazma Shaik
VTU
Chemistry
tutor
tutor
Gaurav Tiwari
APJAKTU
Physics
Get Started

Leave a Reply

avatar
  Subscribe  
Notify of

Customize your course in 30 seconds

Which class are you in?
No thanks.