Understanding multiple recursion

Multiple recursion is when a recursive function calls itself multiple times during its execution. Unlike simple recursion, where the problem space is reduced linearly with every recursive call, multiple recursion branches out into more than one subproblem during the execution of a single function call. The results from some or all of these branches must be considered when calculating the outcome for each step.

The multiple recursion pattern is the classification of problems that can be solved using multiple recursion.

Multiple recursion is when the recursive function calls itself many times.

Multiple recursion

A multiple-recursive function makes more than one recursive function call during its execution, branching off to many subproblems. The recursive function call can be placed either at the top (head recursion) or the end (tail recursion) of the code block. However, in most cases, it is placed in the middle of the code block.

In multiple recursion, the recursive calls are usually made after some initial processing.

Since the recursive function calls are generally made in the middle of the function code block, some processing in the function is already done before making the recursive calls. And so, this processed data is often passed down to the recursive function as the aggregate argument. The data received from all the recursive calls is aggregated and further processed before returning the solution to its caller.

Note that not all multiple recursive functions may pass down an aggregate.