Understanding multidimensional recursion

Multidimensional recursion is a special case of recursion where the recursive function operates on an input that is defined by multiple dimensions, rather than just a single dimension. Unlike simple recursion, where the problem is reduced linearly with each recursive call, multidimensional recursion often explores an n-dimensional space simultaneously, reducing the input in one or more dimensions at once.

Multidimensional recursion

A multidimensional recursion can be seen as a more generalised form of recursion that starts from a starting state and explores multiple other states. A state is a complete description of the current situation in the recursive process that allows the function to continue solving the problem without any additional information.

A state is defined by a set of independent values (values that can vary without constraining each other). The number of values required to define the state uniquely is called the dimension of the state. A state is often visualised as a circle with the values of each dimension inside it as given below.

For example, in a two-dimensional space, the combination of coordinates x and y defines a unique point. The point can be considered a state, and the variables x and y are its dimensions. Similarly, a three-dimensional space has three dimensions x, y and z that define a unique state in it.