Python TCO(Tail call optimization)

Background:

• Tail recursion or TOC refers to the recursive call being last in the last logic instruction in the recursive algorithm.
• When a recursive call is the last statement(Not including any other calculations) executed by the function, we can say this function is tail recursion or TCO.

Example:

Consider a simple function that adds the first N integers using normal recursion, for example: sum(5) = 1 + 2 + 3 + 4 + 5 = 15

def recsum(x):
	if x == 1:
    	return x
	else:
		return x + recsum(x - 1)
recsum(5)

Explanation:

As you can see,every time when I execute this function, the call stack will plus 1, which means if your recursion is deep enough(default number is 1000 in Python), then you function probably will cause the stackoverflow error, in python you won‘t saw this error directly because Python capture this error and raise you a readable message, in this case should be “RuntimeError: maximum recursion depth exceeded”.

here is what really happened in Python interpreter:

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
15