Identifying multidimensional recursion

Multidimensional recursion is the most generic form of recursion that explores an n-dimensional problem space and can solve a wide variety of problems. Most problems that are solved by multidimensional recursion are medium or hard problems that have multiple independent variables defining a problem state. The recursive equation reduces the problem space, ultimately leading to a base case with a known solution. Most multidimensional recursive problems build the solution during the stack unwinding phases in a bottom-to-top order (results from the base cases at the leaves are combined as the recursive calls return up to the root).

Most recursive problems where the solution depends on exploring and combining results across multiple dimensions or states can be solved using multidimensional recursion.

It is important to note that most problems that can be solved using multidimensional recursion can be optimized with dynamic programming.

If the recursive equation for a problem fits in the template of the generic multidimensional recursive equation we learned in the earlier lesson, it can be solved using multidimensional recursion.

The general recursive equation for multidimensional recursion.

Example

Let's consider the following problem as an example to better understand how to identify and solve a problem using multidimensional recursion.