Understanding tail recursion

Tail recursion is the exact opposite of head recursion. A recursive function where the function calls itself at the end of the code block, just before returning to the caller, is a tail-recursive function. It is often used to model problems where the processing in a function call does not depend on results from any deeper recursive call. It is also used when some information has to be passed down from the caller to the called function to process its result, and the solution is built from top to bottom.

Tail recursion

As the name suggests, in tail recursion, the recursive function call occurs at the end (tail) of the code block, just before returning to the calling function. Consequently, all processing for a step is completed before making a recursive call, and no further processing occurs after the recursive call ends. The outcome of processing at each step is often passed down to the recursive call as an argument, typically as an aggregate.

Consider we have a recursive function that takes an input n and an aggregate value from the caller. In its implementation, it processes the input n and aggregate and uses a function g that takes as input n and aggregate to compute aggregate for the next recursive call (for example, if we are computing the sum of 1..n, g is addition that returns aggregate + n). It also uses a function h to reduce the input n for the next recursive call (for example, h(n) = n - 1). This makes the general recursive equation for tail recursion the following form: