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.
Oldest comments (0)