If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

# Properties of recursive algorithms

Here is the basic idea behind recursive algorithms:
To solve a problem, solve a subproblem that is a smaller instance of the same problem, and then use the solution to that smaller instance to solve the original problem.
When computing n, !, we solved the problem of computing n, ! (the original problem) by solving the subproblem of computing the factorial of a smaller number, that is, computing left parenthesis, n, minus, 1, right parenthesis, ! (the smaller instance of the same problem), and then using the solution to the subproblem to compute the value of n, !.
In order for a recursive algorithm to work, the smaller subproblems must eventually arrive at the base case. When computing n, !, the subproblems get smaller and smaller until we compute 0, !. You must make sure that eventually, you hit the base case.
For example, what if we tried to compute the factorial of a negative number using our recursive method? To compute left parenthesis, minus, 1, right parenthesis, !, you would first try to compute left parenthesis, minus, 2, right parenthesis, !, so that you could multiply the result by minus, 1. But to compute left parenthesis, minus, 2, right parenthesis, !, you would first try to compute left parenthesis, minus, 3, right parenthesis, !, so that you could multiply the result by minus, 2. And then you would try to compute left parenthesis, minus, 3, right parenthesis, !, and so on. Sure, the numbers are getting smaller, but they're also getting farther and farther away from the base case of computing 0, !. You would never get an answer.
Even if you can guarantee that the value of n is not negative, you can still get into trouble if you don't make the subproblems progressively smaller. Here's an example. Let's take the formula n, !, equals, n, dot, left parenthesis, n, minus, 1, right parenthesis, ! and divide both sides by n, giving n, !, slash, n, equals, left parenthesis, n, minus, 1, right parenthesis, !. Let's make a new variable, m, and set it equal to n, plus, 1. Since our formula applies to any positive number, let's substitute m for n, giving m, !, slash, m, equals, left parenthesis, m, minus, 1, right parenthesis, !. Since m, equals, n, plus, 1, we now have left parenthesis, n, plus, 1, right parenthesis, !, slash, left parenthesis, n, plus, 1, right parenthesis, equals, left parenthesis, n, plus, 1, minus, 1, right parenthesis, !. Switching sides and noting that n, plus, 1, minus, 1, equals, n gives us n, !, equals, left parenthesis, n, plus, 1, right parenthesis, !, slash, left parenthesis, n, plus, 1, right parenthesis. This formula leads us to believe that you can compute n, ! by first computing left parenthesis, n, plus, 1, right parenthesis, ! and then dividing the result by n, plus, 1. But to compute left parenthesis, n, plus, 1, right parenthesis, !, you would have to compute left parenthesis, n, plus, 2, right parenthesis, !, then left parenthesis, n, plus, 3, right parenthesis, !, and so on. You would never get to the base case of 0. Why not? Because each recursive subproblem asks you to compute the value of a larger number, not a smaller number. If n is positive, you would never hit the base case of 0.
We can distill the idea of recursion into two simple rules:
1. Each recursive call should be on a smaller instance of the same problem, that is, a smaller subproblem.
2. The recursive calls must eventually reach a base case, which is solved without further recursion.
Let's go back to the Russian dolls. Although they don't figure into any algorithms, you can see that each doll encloses all the smaller dolls (analogous to the recursive case), until the smallest doll that does not enclose any others (like the base case).

This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.