Recursion in Python with Different Examples

Recursion in python is the process by which a function calls itself repeatedly until some specified condition has been satisfied. This process is used in place of iterative computations in which each action is stated in terms of a previous result; iterative programs are very big and complex.

In recursion, functions may directly or indirectly call themselves. If the call to a function occurs inside the function, it is called direct recursion. If the function calls another function, which makes a call to the first one, it is called indirect recursion.

How to use recursion in python?

To use recursion, You must declare a function that returns a value. Using that value makes a call to the function within a function. It will work as a loop and gives the desired output.

Syntax

def function_name()
	{
		Statement_1
		Statement_2
		function_name() #recursive call to the function.
	}

Advantages of recursion

1. Avoid unnecessary calling of functions.
2. Solve problems in an easier way than using complex iterative loops.
3. Complex programs can be easily written using recursion.

Disadvantages of recursion

1. Too many recursive functions may confuse the code.
2. The recursive solution is logical, and it isn’t easy to debug and understand.
3. Program execution becomes slower because of the function call and takes time to return a value.

Examples of recursion in python

There are two types of recursion

1. Direct recursion.
2. Indirect recursion.

We will learn examples of both. 

Direct recursion in python

Direct recursion means the function makes the call inside its own body. This concept is the same as direct recursion in python. Let’s understand it with the given an example.

1. Print numbers using recursion

Accept one number from the user and print the numbers from 1 to n using recursion.

Example

def printnum(lr, ur):
  if lr > ur:
      return
  print(lr)
  printnum(lr + 1, ur); #recursive call

n = int(input("Enter number:"))
printnum(1, n)

Output

Enter number:10
1
2
3
4
5
6
7
8
9
10

2. Printing pyramid pattern using recursion in python

Accept the number from the user and print the pyramid pattern using an input. The number of lines in the pyramid should be equal to the number given by the user.

Example

def printn(num):
   if (num == 0):
       return
   print("*", end=" ")
   printn(num - 1) #recursive call to printn function

def pattern(n, i):
   if (n == 0):
       return
   printn(i)
   print("\n", end="")
   pattern(n - 1, i + 1) #recursive call to pattern function

n = int(input("Enter number:"))
pattern(n, 1)

Output

Enter number:7
* 
* * 
* * * 
* * * * 
* * * * * 
* * * * * * 
* * * * * * *

3. Print Fibonacci number using recursion in python

Accept a number of terms from the user and print the Fibonacci series using recursion.

Example

def Fibonacci(n):
  if n < 0:
      print("Incorrect input")

  elif n == 0:
      return 0 #base case

  elif n == 1 or n == 2:
      return 1 #base case

  else:
      return Fibonacci(n - 1) + Fibonacci(n - 2) #recursive call to the function

n = int(input("Enter number of terms: "))

i = 0
for i in range(n):
  print(Fibonacci(i),end="\t")

Output

Enter number of terms: 5
0	1	1	2	3

Indirect recursion in python

An indirect recursion is a process in which two or more functions call mutually call each other. Both the functions must have a base case. 

1. Print numbers using an indirect recursive call

Accept range from user and print numbers using 2 functions the first function will can the second function to print the number and after printing the second function should call the first function. This process should execute until the function reaches the upper limit.

Example

def printn(lr, ur):
 if lr <= ur:
   print(lr)
   lr += 1
   fun(lr, ur) #indirect recursive call
 else :
    return

def fun(lr, ur):
if lr <= ur:
  print(lr)
  lr += 1
  printn(lr, ur) #indirect recursive call
else :
    return

n = int(input("Enter number:"))
printn(1, n)

Output

Enter number:5
1
2
3
4
5