Recursion in Python

Previous
Next

Function Recursion

Recursion is a process of calling a function from within its body. This type of function is called a recursive function.

Note: In the program, some arrangement must be made to terminate the recursive loop, and otherwise it will end up in an infinite loop.

Recursion

Uses of Recursion

Recursion can be used in these scenarios:

  1. When we can solve a problem by breaking it into similar problems. Example, factorial of a number, sum of digits of an integer.
  2. When we have an unknown number of loops. Example, finding all combinations of 1 to n.

Let’s understand with a simple example

The below example is a simple example to understand recursion. Here we have a function numbers() that calls itself until “n” is not equal to 1. As soon as “n” reaches 1, it returns 1. This is the point where we terminate the recursion. Once the recursive calls are terminated, it will start executing the print statement and print the numbers in reverse order from 5 to 1.

In [1]:
def numbers(n):
    print(n)
    if n == 1:
        return 1 #terminates recursion
    else:
        numbers(n-1) #recursive call
    
numbers(5)

5
4
3
2
1

Example – Factorial of a number

In this example, we will calculate the factorial of the number using the recursive functions calls. The factorial of number n is calculated as:

n! = n x (n-1) x (n-2) x … x 2 x 1

In this example, 1 is returns when n reaches 0, this is the point there we terminate the loop. When the n is greater than 0, the else case is executed. Each time, it will decrement “n” by 1.

In [1]:
def factorial(n):
    if n == 0:
        return 1
    else:
        num = n * factorial(n-1)
    return num


result = factorial(5)
print(result)

120

Types of Recursion

There can be two types of recursion

  1. Head recursion
  2. Tail recursion

Head Recursion

In this, a recursive call to the function is made before the other processing of the function.

So, in practice, the code for the last recursive call will execute first.

In [1]:
def head_recursion(n):
    if n==0:
        return
    else:
        head_recursion(n-1)
        print(n)


head_recursion(10)

1
2
3
4
5
6
7
8
9
10

Tail Recursion

In this, a recursive call to the function is made after the other processing of the function.

Here, the code for the first recursive call with execute first.

In [1]:
def tail_recursion(n):
    if n==0:
        return
    else:
        print(n)
        tail_recursion(n-1)


tail_recursion(10)

10
9
8
7
6
5
4
3
2
1

Maximum Recursion Depth

The default recursion limit is set to 10 ** 4, so if we try a recursive function with very large numbers, then it will result in an RecursionError error.

We get this error because in head recursion, we get the result of our calculation once we have returned from every recursive call.

Python is flexible enough to allow us to change the recursion limit to some larger number, for example 10 ** 6 to handle large inputs without any error.

Advantages and Disadvantages of Recursion

Advantages

  1. Code looks clean and effective.
  2. It is better than nested iterations for generating sequence.
  3. We can split a complicated task into smaller sub-tasks.

Disadvantages

  1. Expensive on memory and time.
  2. Bit difficult to debug recursive functions.
  3. Sometimes it is tough to build recursion logic.

References

  1. Recursive Functions
Previous
Next