How do you optimizing recursive functions

Let's remember

Recursive functions, a common topic when you are studying your career, like informatic engineer o related careers, but it's even more common learn only the fundamental:

A recursive function is when the function call itself for reduce a big problem to another each more small until reaching a base case.

A classic example is calculate the factorial of a positive number:

def factorial(n):    

    if n == 0:
        return 1

    return n * factorial(n - 1)

print(factorial(4))

The bad

The compiler needs to stack each recursive function called in the call stack, until find the base case. Then, return to resolve each pending operation that left in the call stack:

# call stack simulation:
factorial(4)
  4 * factorial(3)
    3 * factorial(2)
      2 * factorial(1)
        1 * factorial(0)
          return 1
            1 * 1 -> return 1
        2 * 1 -> return 2
    3 * 2 -> return 6
  4 * 6 -> return 24

>>> 24

The above implementation could be easy to overflow the call stack with big numbers.

Tail recursion

This is the part that ommited in many case when are talking about recursion. Exist a way to optimizing the recursive functions and the tip is: Not leave pending operations when your call the function on mode recursive.

Now, let's optimice the above example:

def factorial(n, acum=1):

    if n == 0:
        return acum

    return factorial(n - 1, acum * n)

print(factorial(4))

# >>> 24

What changed?

The new acum variable help as an accumulator for the calculation of the factorial. Next, compare the return statement of the functions:

• Not optimized example: return n * factorial(n - 1)
• Optimized example: return factorial(n - 1, acum * n)

You need to find a way for not leave pending operations if you want tail recursion.

With the recursive funtion optimized, the compiler doesn't need to stack each recursive function called, only change the value of the entry parameters function and execute until the base case is true:

# call stack simulation:
factorial(4, 1)
factorial(3, 4)
factorial(2, 12)
factorial(1, 24)
factorial(0, 24)
return 24
>>> 24

There is no more fear that the call stack overflowed.

Support for tail recursion

Unfortunately, not all programming language support tail recursion in your compiler/interpreter. Python is one of them, but there are some libraries that help to simulate this behavior with decorators.

This article on Wikipedia list some programing languages that support tail recursion.

Anyway, it's fun to see how we can improve the algorithmic complexity of a program and I hope you enjoyed it too.

Thanks!

Follow me on Twitter.