Search⌘ K
Home
Courses
A Visual Introduction to Algorithms

Properties of recursive algorithms

Learn the fundamental properties of recursive algorithms by exploring how solving smaller instances leads to solving the original problem. Understand the importance of progressively smaller subproblems and hitting base cases through clear examples like factorial calculations.

We'll cover the following...

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!n!, we solved the problem of computing n!n! (the original problem) by solving the subproblem of computing the factorial of a smaller number, that is, computing (n−1)!(n-1)! (the smaller instance of the same problem), and then using the solution to the subproblem to compute the value of n!n!.

In order for a recursive algorithm to work, the smaller subproblems must eventually arrive at the base case. When computing n!n!, the subproblems get smaller and smaller until we compute 0!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)!(-1)!, you would first try to compute (−2)!(−2)!, so that you could multiply the result by −1−1. But to compute (−2)!(−2)! ...