Main content
Computer science
Course: Computer science > Unit 1
Lesson 6: Recursive algorithms- Recursion
- The factorial function
- Challenge: Iterative factorial
- Recursive factorial
- Challenge: Recursive factorial
- Properties of recursive algorithms
- Using recursion to determine whether a word is a palindrome
- Challenge: is a string a palindrome?
- Computing powers of a number
- Challenge: Recursive powers
- Multiple recursion with the Sierpinski gasket
- Improving efficiency of recursive functions
- Project: Recursive art
© 2023 Khan AcademyTerms of usePrivacy PolicyCookie Notice
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:
- Each recursive call should be on a smaller instance of the same problem, that is, a smaller subproblem.
- 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?
- could recursion be used to sort an array of numbers like we have previously?(3 votes)
- Definitely! Merge Sort is a popular sorting algorithm where recursion is widely used to implement it.(17 votes)
- 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)
- 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(4 votes)
- 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)
- 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)
- 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)- looks like your just missing one assert (you should have 4 in total)(4 votes)
- Why does the recursive calls must eventually reach a base case?(0 votes)
- 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 toprintln("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 toprintln("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)
- 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)- An if/else statement will only execute one set of contained statements. You can't have both the if clause and else clause running their code.(2 votes)
- What are the two different algorithms for a factorial problem?(1 vote)
- The Russian dolls example made things very clear from the beginning(1 vote)
- "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)- 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)
- how can i get previous node by coding in recursive method(1 vote)