Python Recursion Example – Recursive Functions

When a function calls itself, it’s called a recursive function. In this tutorial, we will learn how to write Python recursion function.

What is Recursion in Python?

When a function is defined in such a way that it calls itself, it’s called a recursive function. This phenomenon is called recursion. Python supports recursive functions.

Do we really need Recursive Functions?

The recursion is very similar to a loop where the function is called in every iteration. That’s why we can always use loops as a replacement for Python recursion function.

But, some programmers prefer recursion over loops. It’s a matter of choice mostly and you are free to either use loops or recursion.

Python Recursion Function Examples

Let’s look into a couple of examples of recursion function in Python.

1. Factorial of an Integer

The factorial of an integer is calculated by multiplying the integers from 1 to that number. For example, the factorial of 10 will be 1*2*3….*10.

Let’s see how we can write a factorial function using the for loop.

def factorial(n):
    result = 1

    for i in range(1, n + 1):
        result = result * i

    return result


print(f'Factorial of 10 = {factorial(10)}')
print(f'Factorial of 5 = {factorial(5)}')

Let’s see how can we change the factorial() function to use recursion.

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n - 1)


print(f'Factorial of 10 = {factorial(10)}')
print(f'Factorial of 5 = {factorial(5)}')

The below image shows the execution of the recursive function.

2. Fibonacci Series

The Fibonacci series is the sequence of numbers where each number is the sum of two preceding numbers. For example – 1, 1, 2, 3, 5, 8, 13, 21 and so on.

Let’s look at a function to return Fibonacci series numbers using loops.

def fibonacci(n):
    """ Returns Fibonacci Number at nth position using loop"""
    if n == 0:
        return 0
    if n == 1:
        return 1
    i1 = 0
    i2 = 1
    num = 1
    for x in range(1, n):
        num = i1 + i2
        i1 = i2
        i2 = num
    return num


for i in range(10):
    print(fibonacci(i), end=" ")

# Output: 0 1 1 2 3 5 8 13 21 34 

Here is the implementation of the fibonacci() function using recursion.

def fibonacci(n):
    """ Returns Fibonacci Number at nth position using recursion"""
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)


for i in range(10):
    print(fibonacci(i), end=" ")

# Output: 0 1 1 2 3 5 8 13 21 34 

Here recursive function code is smaller and easy to understand. So using recursion, in this case, makes sense.

What is the Base Case in Recursion?

While defining a recursive function, there must be at least one base case for which we know the result. Then every successive recursive function call must bring it closer to the base case. This is required so that eventually the recursive calls terminate. Otherwise, the function will never terminate and we will get out of memory error.

You can check this behavior in both the above examples. The recursive function call arguments are getting closer to the base case.

Advantages of Recursion

• Sometimes recursion reduces the number of lines of code.
• The recursion code looks simple.
• If we know the base case, then using recursion in a function is easier.

Disadvantages of Recursion

• If not implemented properly, the function will never terminate.
• Understanding recursion is more confusion when compared to loops.

Recursion or Loops?

It’s a matter of personal choice. I always prefer loops over recursion. I haven’t seen any example where we can’t use loops and have to use recursion only.

References:

• Wikipedia