Recursion in Python refers to the concept when a function is called by itself one or more times.

Syntax

def fun():
    // statements
    fun()

Consider a scenario where we want calculate the factorial of n = 5, let’s see how it goes :

factorial(5) :
-> 5 * factorial(4)
–> 5 * 4 * factorial(3)
—> 5 * 4 * 3 * factorial(2)
—-> 5 * 4 * 3 * 2 * factorial(1)
—–> 5 * 4 * 3 * 2 * 1 = 120

Here, you must be able to catch the common pattern.

So, recursive formula to calculate factorial of any number ‘n’ is given as :

factorial(n) = n * factorial(n-1)

Here, function factorial() is calling itself with different values of ‘n’.

One thing to note is that every recursive function requires a break-down condition. A break-down condition is a condition which breaks down the program flow once intended purpose is completed.

If recursive function, does not have any break-down condition then, it will become an infinite loop.

Program : To calculate the factorial of a given number using recursion

def factorial(n):
    if n == 1: # break-down condition
        return 1 
    else: 
        return n * factorial(n-1)
print(factorial(5))      

Above function factorial() evaluates the factorial of 5.

if n == 1 : 

Above line is a break-down condition. This means that program flow will stop when ‘n’ becomes 0 and final value is returned.

Let’s try to break this :

Recursion has two phases :

1. Winding Phase : This phase runs until desired condition is fulfilled.

2. Unwinding Phase : Once winding phase gets over, control is transferred back to original call, this is unwinding phase.

Types of Recursion in Python

Recursion in Python is of two types :

1. Direct Recursion

2. Indirect Recursion

Let’s explore them one-by-one

Direct Recursion

Direct Recursion is a type of recursion in which a function explicitly calls itself, usually with a different set of values. It is further divided into 3 types :

1. Tail Recursion

2. Non Tail Recursion

3. Tree Recursion

Tail Recursion

Tail Recursion occurs if a recursive function calls itself and the function call is the last statement to be processed in the function before returning having reached the base case. After processing the call, function returns control back to the parent function call.

Program : To print counting from 1 to 10 with the help of tail recursion.

def counting(n):
    if n == 11: # break-down condition
        return  
    else: 
        print(n)
        counting(n+1)
counting(1)     

O/P

1
2
3
4
5
6
7
8
9
10

In the above code, function counting() has a recursive call as a last statement. Here, the program will terminate when
n = 11, this is the break-down condition or also known as base condition of a program.

Order of Execution : print(1) -> counting(1) -> print(2) -> counting(2) -> print(3) -> counting(3) -> print(4) -> counting(4) -> print(5) -> counting(5) -> print(6) -> counting(6) -> print(7) -> counting(7) -> print(8) -> counting(8) -> print(9) -> counting(9) -> print(10) -> counting(10) -> n == 11

Non Tail Recursion

Non Tail Recursion occurs if a recursive function calls itself and the function call is not the last statement to be processed in the function. In non tail recursion, there are some operations executed even after the recursive call.

Program : To print counting from 1 to 10 with the help of non tail recursion.

def counting(n):
    if n == 0: # break-down condition
        return  
    else: 
        counting(n-1) # recursive call is not the last statement
        print(n)
counting(10)     

O/P

1
2
3
4
5
6
7
8
9
10

In the above code, function counting() has a recursive call but not as a last statement. Here, the program will terminate when
n = 0, this is the break-down condition or also known as base condition of a program.

Order of execution :

counting(10) -> counting(9) -> counting(8) -> counting(7) -> counting(6) -> counting(5) -> counting(4) -> counting(3) -> counting(2) -> counting(1) -> n == 0 condition satisfies -> Now print statement will come into picture.

counting(1) will return 1, counting(2) will return 2, counting(3) will return 3 and so on.

Tree Recursion

Tree Recursion in Python is a type of recursion in which a function is called two or more times in the same function.

Program : To print n-th term of fibonacci series (1 1 2 3 5 8 13 21 …) in Python using Tree Recursion.

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(4))     

O/P : 3

Order of Execution : Please refer to the below image in order to trace the execution

Indirect Recursion

Indirect Recursion is a type of recursion where two or more functions are involved in mutual-invocation. This means that, if function fun1() calls another function fun2() and, fun2() calls fun1() again, then this is termed as indirect recursion.

def fun1():
    # statements 
    fun2()
def fun2():
    # statements 
    fun1() 

Program : To implement Indirect Recursion

def fun1(a):
    if a % 2 == 0:
        print(a) 
        return 
    a += 1
    fun2(a)
def fun2(a):
    if a % 2 == 0:
        print(a) 
        return
    a += 2
    fun1(a)
fun1(11)    

O/P : 12

In the above program, our task is to terminate the program when ‘a’ becomes even.
Function fun1() increments value by 1 then calls fun2() and function fun2() increments value by 2 then calls fun1().

Application of Recursion in Python

Recursive algorithms are usually shorter and are used to solve many complex real world problems. Some of them are :

1. Postfix, Prefix, Infix Conversion
2. Tower of Hanoi
3. Parenthesis Matching
4. N-Queen’s Problem
5. Depth First Search, Breadth First Search

Recursive Algorithms have higher runtime complexities.

Difference between Iteration and Recursion

That’s all about Recursion in Python.