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 $(n-1)!$ (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 $(-1)!$, you would first try to compute $(−2)!$, so that you could multiply the result by $−1$. But to compute $(−2)!$ ...