Identifying tail recursion

Tail recursion is another fundamental form of recursion and can be seen as analogous to iterative loops. Most problems that are solved by tail recursion are easy or medium problems, where results are progressively built as recursive calls are made. All the processing in a function happens before the recursive call is made, and processed data is often passed down the recursive calls. The results in case of tail recursion are built in the top-to-bottom order.

Most recursive problems that allow carrying forward all the needed information in parameters (like an aggregate or some other state) and require no extra work after the recursive call can be solved with tail recursion.

It is important to note that most problems that can be solved using tail recursion can also be solved either iteratively or using other forms of recursion.

If the recursive equation for a problem fits in the template of the generic tail recursive equation, it can be solved by tail recursion.

The general recursive equation for tail recursion.

Example

Liking the course? Check our discounted plans to continue learning.

Subscribe