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.

Main content

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.

Want to join the conversation?

  • mr pink red style avatar for user Jean Rambo
    Why, for (n+1)!, would you have to compute (n+2)!, (n+3)!, etc. ? Factorial would multiply all the numbers up to n+1, not larger.
    (4 votes)
    Default Khan Academy avatar avatar for user
    • blobby green style avatar for user Tapaswini Kodavanti
      To compute n!, the example demonstrates an alternate way of finding it by finding (n+1)! and dividing by (n+1). However, to find (n+1)!, recursion would prompt it to find (n+2)!. To find (n+2)!, the function would proceed to (n+3)!. It is only getting farther away from the base case, so this method would not work. Hope this is useful as well
      (3 votes)
  • leafers sapling style avatar for user Hannan Ali
    Is recursion useful in tree structures because we can go from one parent tree to a child tree, and child tree is always lower than the parent tree?
    (1 vote)
    Default Khan Academy avatar avatar for user
    • mr pants teal style avatar for user Robert
      Yes, I would say recursion is very useful when dealing with data structures like trees. In fact any time a data structure can be viewed as being composed in some way of several parts, some of which may also be instances of the same structure, recursion will likely prove useful. Even more abstractly, recursion will prove useful as a way of thinking about problems which can be broken down into similar, but in some way easier, problems. Recursion in this sense becomes almost like an attitude which gladly takes on all tasks, so long as they can be attacked as smaller subtasks of the same nature. Hope that helps!
      (8 votes)
  • leaf green style avatar for user 23atesfaye
    I really need help with this code can anyone help me


    var factorial = function(n) {
    // base case:
    if (n===0) {
    return 1;
    }

    // recursive case:
    return factorial(n-1) * n;
    };

    println("The value of 0! is " + factorial(0) + ".");
    println("The value of 5! is " + factorial(5) + ".");

    Program.assertEqual(factorial(0), 1);
    Program.assertEqual(factorial(5), 120);

    Program.assertEqual(factorial(3), 6);
    (2 votes)
    Default Khan Academy avatar avatar for user
  • piceratops seed style avatar for user kaiden morrow
    Why does the recursive calls must eventually reach a base case?
    (0 votes)
    Default Khan Academy avatar avatar for user
    • hopper cool style avatar for user Neil And Chase
      Otherwise the program would never end, and that would eventually take up more memory than is available for the program. For example, let's say I had the program:
      var recurse = function(num) {
      if (num > 0) {
      recurse(num-1);
      println("recursion");
      }
      };

      If I were to limit this to three recursions, the actual code run would look like this:
      var num = 3;
      if (num > 0) { //num == 3
      num--;
      if (num > 0) { //num == 2
      num--;
      if (num > 0) { //num == 1
      num--;
      if (num > 0) {
      } //num == 0
      println("recursion");
      }
      println("recursion");
      }
      println("recursion");
      }

      Notice that it has to remember to println("recursion"); for every time it recursed (it also has to remember to end the function, but that isn't represented in the code). If I had no base case, this would go on forever, and the number of times it has to remember to println("recursion"); and end the function would eventually exceed the allotted memory and give (if I remember correctly) a stack overflow error.

      Hope this helps!
      Neil
      (7 votes)
  • leafers ultimate style avatar for user David
    could recursion be used to sort an array of numbers like we have previously?
    (2 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user mohamad
    i have a question from previous challenge
    it was my code which was correct:
    var factorial = function(n) {
    // base case:
    if (n<=1){
    return 1;
    }
    else{
    return n * factorial(n-1); }

    };
    when the "n" value is any positive value(not zero)the computer reads two return statement the first one is" return 1;"and the other one is "return n * factorial(n-1);"but how does it know that it should keep the value of 0! and return the second return statmant .and not return both?
    (1 vote)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user Anummujib
    What are the two different algorithms for a factorial problem?
    (1 vote)
    Default Khan Academy avatar avatar for user
  • eggleston orange style avatar for user Anas Sallam
    The Russian dolls example made things very clear from the beginning
    (1 vote)
    Default Khan Academy avatar avatar for user
  • starky sapling style avatar for user Piggy Backride
    "n! = (n+1)! / (n+1) n!=(n+1)!/(n+1). This formula leads us to believe that you can compute n! n! by first computing (n+1)! (n+1)! and then dividing the result by n+1 n+1n, plus, 1" -

    why does it lead you to believe that? That is just weird. (n+1)!/(n+1) = (n+1)n(n-1)*...1/(n+1), from where (n+1) can be safely removed and we get n!=n(n-1)*...*1.
    (1 vote)
    Default Khan Academy avatar avatar for user
    • leafers ultimate style avatar for user Jason Bit
      It's poorly laid out, but does make sense. Let's rewrite it more clearly.

      Step 1 (take the formula)
      n! = n(n-1)!

      Step 2 (divide both sides by n)
       n!
      --- = (n-1)!
      n

      Step 3 (let m = n+1 and substitute with m)
       m!               (n+1)!                 (n+1)!
      --- = (m-1)! => ------ = (n+1-1)! => ------ = n!
      m n+1 n+1

      Step 4 (... leads us to believe you can compute n! ...)
           (n+1)!
      n! = ------
      n+1

      So basically, *n!* can be computed by first computing the numerator (n+1)! then dividing by the denominator n+1, is basically what that sentence is trying to say.
      (1 vote)
  • blobby green style avatar for user juhi sinha
    how can i get previous node by coding in recursive method
    (1 vote)
    Default Khan Academy avatar avatar for user