Key components of recursion

Now that we have a basic idea of how recursion works, let's dive deeper into its more formal mathematical definition. We will look at the two conditions the problem must satisfy in order to have a recursive solution.

Recursive structure

A problem is said to have a recursive structure if it can be broken down into smaller subproblems, solutions to which can be used to solve the bigger problem. These subproblems should be the same as the original problem but on a smaller subset of inputs. Continuing our previous example of the atm queue, a person can know their position by solving the same problem for the person ahead of them.