Understanding head recursion
Head recursion is when a recursive function calls itself at the beginning of the code block, just after checking for base cases. Since the function is called at the beginning, all deeper recursive calls (till the base case) are finished before its processing begins. The result of each step is often processed using the results from the recursive steps below it, and so head recursion is used in cases where the solution has to be built from bottom to top.
The solution is built from bottom to top during stack unwinding in head recursion.
Head recursion
Head recursion is when the recursive function call is placed at the top (head) of the code block, just after checking the base case. As a consequence, every step in the series of recursive calls makes another recursive call before any processing starts, and this process is repeated until it hits the base case.
Consider we have a recursive function f that takes an input n from the caller. In its implementation, it uses a function h that reduces the input n for the next recursive call and a function g that processes the result from the recursive call to get the solution for the call to f. This makes the general recursive equation for head recursion the following form:
The general recursive equation for head recursion.
The pseudocode for the general recursive equation above is as follows.
Liking the course? Check our discounted plans to continue learning.