Recursive Functions in Python

Posted by AbundantCode

This tutorial will teach you about Python recursive functions and how to use them to simplify your code.

A recursive function is one that calls itself until it stops.

The fn() function below is a recursive function because it calls itself:

def fn():
    # ...
    fn()
    # ...

The #… in the fn() function denotes other code.

A recursive function must also have a condition that causes it to stop calling itself. As a result, you must include an if statement like this:

def fn():
    # ...
    if condition:
        # stop calling itself
    else:
        fn()
    # ...

A recursive function is typically used to break down a large, difficult-to-solve problem into smaller, simpler problems.

Trees, graphs, and binary searches are all examples of data structures and algorithms that use recursive functions.

A basic Python recursive function example

Assume you need to create a countdown function that goes from a certain number to zero.

If you execute the function that counts down from 3, for example, you’ll get the following result:

3
2
1

The count down() method is defined as follows:

def count_down(start):
    """ Count down from a number  """
    print(start)

If you use the count down() method right now, you’ll see:

count_down(3)

… Only the number 3 will be displayed.

To demonstrate the numbers 3, 2, and 1, do the following:

To show the number 3, first call count down(3).
Second, use the count down(2) function to display the number 2.
Finally, use count down(1) to display the number one.
To accomplish this, define a logic inside the count down() method to call the function count down() with arguments 2 and 1.

You must make the count down() function recursive to accomplish this.

The following code declares a recursive count down() method and calls it with the number 3 as a parameter:

def count_down(start):
    """ Count down from a number  """
    print(start)
    count_down(start-1)


count_down(3)

You’ll get the following error if you run the programme:

RecursionError: maximum recursion depth exceeded while calling a Python object

The reason for this is that count down() keeps calling itself until the system stops it.

When the number reaches zero, you must cease counting down. To accomplish so, add the following condition:

def count_down(start):
    """ Count down from a number  """
    print(start)

    # call the count_down if the next
    # number is greater than 0
    next = start - 1
    if next > 0:
        count_down(next)


count_down(3)

Output

3 2 1

The count down() function is only used in this case when the next number is bigger than zero. In other words, it stops calling itself if the next number is zero.

Using a recursive function to calculate the sum of a sequence

Assume you need to find the sum of a series ranging from 1 to 100. A for loop with the range() function is a straightforward way to accomplish this:

def sum(n):
    total = 0
    for index in range(n+1):
        total += index

    return total


result = sum(100)
print(result)

Output

5050

The total of the sequence from 1 to n can be calculated using the recursion approach as follows:

sum(n) = sum(n) (n-1)
n-1 + n-2 Equals sum(n-1)…
sum(0) = 0
As long as the parameter is higher than zero, the sum() function keeps calling itself.

The recursive version of the sum() function is defined as follows:

def sum(n):
    if n > 0:
        return n + sum(n-1)
    return 0


result = sum(100)
print(result)

The recursive function, as you can see, is much shorter and easier to read.

The sum() function will be even more concise if you utilise the ternary operator:

def sum(n):
    return n + sum(n-1) if n > 0 else 0


result = sum(100)
print(result)
Tags: