Tail Recursion in Python

1. Recursion in Python
2. Tail Recursion in Python
3. Call Tail-Recursive Function in Python
4. Benefits of Tail-Recursive Functions

In today’s tutorial, we will learn about tail recursion by going through recursion and its types. Further, we will also learn how to call tail recursion in Python and explore some benefits of using it.

Recursion in Python

In computer science, recursion is a problem-solving method in which a function calls itself in the body until a specific condition is met.

It is one of the valuable methods, and it has a lot of real-life use cases; however, it has some limitations, and that is its space and time complexity. Let’s see an example of a recursion below.

Example Code:

def factorial(n):
    if n == 1 or n == 0:
        return 1
    else:
        return n * factorial(n - 1)  # recursive call


num = 4

# In this case factorial is 4x3x2x1 = 24
print(f"The factorial of {num} is {factorial(num)}")

Output:

The factorial of 4 is 24

Recursion uses a stack to keep the local variables, each run of the recursions increases its size, and the stack size is limited. It is the reason the developers started thinking about some optimized solutions.

It’s suitable only for small numbers; that’s why the developers came up with the optimized solution of simple recursion, and that is Tail Recursion.

Types of Recursions

When it comes to recursive functions, there are two main types:

1. Head recursion
2. Tail recursion

Head recursion is when the function calls itself at the beginning, while tail recursion is when a function calls itself at the end of the recursion.

Both have benefits and drawbacks, but tail recursion is generally considered more efficient. Let’s understand it in more detail below.

Tail Recursion in Python

Tail recursion in Python is an optimized solution to simple recursion; it allows unlimited recursion without raising any stack overflow error.

But before going into the details of tail call recursion, let’s understand the definition of tail call recursion; the call means we are considering calling the function, whereas the tail means that the last. So, calling the tail-recursive method means the function repeatedly calls itself from the end of the function.

Nowadays, most programming languages are tail-recursive, which means they are making optimizations to the recursive functions.

Call Tail-Recursive Function in Python

There are two ways to call a tail-recursive function in Python. The first is to use the return keyword, and the second is to use the yield keyword.

Use the return Keyword to Call a Tail-Recursive Function

Firstly, you can use the return keyword to return a value from a function. However, you must be careful with this keyword, as it will immediately terminate the function.

It means you can only use it if you are sure the function will never need to be called again. Remember, when we use the’ return’ keyword, the function returns the last computed value.

It is the most common way to call a tail-recursive function. For example, see a code fence below.

Example Code:

def trisum(n, csum):
    while True:  # Change recursion to a while loop
        if n == 0:
            return csum
        n, csum = n - 1, csum + n  # Update parameters instead of tail recursion


trisum(1000, 0)

Output:

500500

Use the yield Keyword to Call a Tail-Recursive Function

Another way to call tail-recursive functions is to use the yield keyword. This keyword allows you to return a value from a function without terminating the function.

You can call the function repeatedly, returning a different value each time. It is handy for functions that need to return a large number of values.

When using the yield keyword, the function will yield the last computed value. It is a less common way to call a tail-recursive function, but it can be helpful in some cases.

Example Code:

def lprint(a):
    if isinstance(a, list):
        for i in a:
            yield from lprint(i)
    else:
        yield a


b = [[1, [2, 3], 4], [5, 6, [7, 8, [9]]]]
for i in lprint(b):
    print(i)

Output:

1
2
3
4
5
6
7
8
9

Benefits of Tail-Recursive Functions

Tail-recursive functions are a type of recursive function in which the last statement in the function is a call to the recursive function.

This function is more efficient than non-tail recursive functions because it doesn’t require the function to keep track of the intermediate values of the recursive calls.

It makes tail-recursive functions more efficient and easier to understand. There are many benefits to using tail-recursive functions.

1. One of the main benefits of tail recursion is that it is easier to optimize. Because the tail call is the last thing that happens in the function, the compiler can optimize it more easily. It means that tail recursive functions can be more efficient in terms of time and space.
2. Another benefit of tail recursion is that it is often easier to understand. Because the recursive call is the last thing that happens in the function, it is easier to see what is happening. It can make tail recursive functions easier to debug and maintain.
3. They are more efficient than non-tail recursive functions because they avoid the need to keep track of intermediate values.
4. They are easier to reason about because the function call stack is always empty at the end of the function. Also, tail-recursive functions can be more easily parallelized.
5. We can easily convert them to iterative programs, which can be more efficient in some cases.
6. It can make the function run faster and use less memory. Also, it can make it easier to write correct code.