Recursion in Python

  • Python

Recursion is a process where a function can call itself. Python also supports recursion function, which means a function in python can call itself.

Let’s understand this using a simple example where the function will print the sum of all digits from 1 to wherever specified.

def recurse_sum(x):
    if x == 1:
        return 1
    else:
        return (x + recurse_sum(x-1))


num = 5
print("The recursive sum from 0 to", num, "is", recurse_sum(num))

Output :

The recursive sum from 0 to 5 is 15

In the above example, we are calling the recursive_sum() function inside itself where the value of argument is decreasing by 1 every time the function runs and it stops as it reached the base condition that is if the number is equal to 1.

If we do not define a base condition, it will keep on running and it will call itself infinitely. By default, python has a depth limit of 1000 for the recursion function and it will give you an error for Recursion Error. But this limit can be changed by using sys module.

RecursionError: maximum recursion depth exceeded

Let’s take a look at another example of recursive function for factorial.

def fact(i):
  if i == 0:
    return 1
  else:
    return i * fact(i-1)

num = 6
print("The factorial of", num, "is", fact(num))

Output :

The factorial of 6 is 720

Just like previous example added every number to the previous number, this function multiplies each number to the factorial of the number 1 less than itself until the value reached 1 which is mapped to the the base condition. Take a look at the step by step process of the working.

fact(6)         
6 * (5)
6 * 5 * fact(4)
6 * 5 * 4 * fact(3)
6 * 5 * 4 * 3 * fact(2)
6 * 5 * 4 * 3 * 2 * fact(1)
6 * 5 * 4 * 3 * 2 * 1
720