Identifying head recursion

Head recursion is the most basic form of recursion and is relatively easy to understand and identify. Most problems that are solved by head recursion are easy problems where we need to know the solution to smaller sub-problems before we can start processing the solution to larger problems. The actual processing of results generally happens during the stack unwinding phase in a bottom-to-top order (from the base case back up to the top-level call).

Most recursive problems that allow deferring any processing until we have the results of smaller sub-problems can be solved with head recursion.

It is important to note that most problems that can be solved using head 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 head recursive equation (the template introduced in the previous lesson, where the recursive call sits at the top and its result is combined with the current input by a function g), it can be solved by head recursion.

The general recursive equation for head recursion.