Tail Vs Non-Tail Recursion

Tail recursion

We call a function is tail recursion if that function is the final instruction in the program

For example, the following code can be considered as tail recursion:

def tailRecursionSumList(arr: List[int]):
    def accumulate(currIndex: int, accumulation: int) -> int: # anonymous function
        if (currIndex >= len(arr)):
            return accumulation
        return accumulate(currIndex + 1, accumulation + arr[currIndex])
    return accumulate(0, 0)

As a result, it leaves no stack calls after the recursion call itself, the result added up to the tail and return from the tail. Hence the name tail-recursion.

For languages such as C, C++ tails recursion can be optimised by compiler

Non-tail recursion

A function is called non-tail recursion if there are instruction after the recursion call. The same function above can be written as non-tail recursion as follow:

def nonTailRecursionSumList(arr: List[int]):
    def accumulate(currIndex):
        if (currIndex >= len(arr)):
            return 0

        return arr[currIndex] + accumulate(currIndex + 1)

    return accumulate(0)

In here, as we can see, after the recursion, it goes back to the stack that called that recursion instruction to continue calculation and return back up to the parent