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.

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

could recursion be used to sort an array of numbers like we have previously?

Definitely! Merge Sort is a popular sorting algorithm where recursion is widely used to implement it.

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);

looks like your just missing one assert (you should have 4 in total)

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?

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!

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?

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.

Why does the recursive calls must eventually reach a base case?

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

Main content

Properties of recursive algorithms

Q: 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?

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.

Google Classroom

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?

Sort by:

David
Posted 8 years ago. Direct link to David's post “could recursion be used t...”
could recursion be used to sort an array of numbers like we have previously?
Button navigates to signup pageButton navigates to signup page
(3 votes)
Answer
- mail.jose.sanchez
  Posted 8 years ago. Direct link to mail.jose.sanchez's post “Definitely! Merge Sort is...”
  Definitely! Merge Sort is a popular sorting algorithm where recursion is widely used to implement it.
  Button navigates to signup page
  (17 votes)
Jean Rambo
Posted 8 years ago. Direct link to Jean Rambo's post “Why, for (n+1)!, would yo...”
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.
Button navigates to signup pageButton navigates to signup page
(4 votes)
Answer
- Tapaswini Kodavanti
  Posted 3 years ago. Direct link to Tapaswini Kodavanti's post “To compute n!, the exampl...”
  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
  Button navigates to signup page
  (4 votes)
Hannan Ali
Posted 7 years ago. Direct link to Hannan Ali's post “Is recursion useful in tr...”
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?
Button navigates to signup pageButton navigates to signup page
(1 vote)
Answer
- Robert
  Posted 7 years ago. Direct link to Robert's post “Yes, I would say recursio...”
  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!
  Button navigates to signup page
  (8 votes)
23atesfaye
Posted 4 years ago. Direct link to 23atesfaye's post “I really need help with t...”
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);
Button navigates to signup pageButton navigates to signup page
(2 votes)
Answer
- Cameron
  Posted 4 years ago. Direct link to Cameron's post “looks like your just miss...”
  looks like your just missing one assert (you should have 4 in total)
  Button navigates to signup page
  (4 votes)
kaiden morrow
Posted 6 years ago. Direct link to kaiden morrow's post “Why does the recursive ca...”
Why does the recursive calls must eventually reach a base case?
Button navigates to signup pageButton navigates to signup page
(0 votes)
Answer
- Neil And Chase
  Posted 6 years ago. Direct link to Neil And Chase's post “Otherwise the program wou...”
  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
  Button navigates to signup page
  (7 votes)
mohamad
Posted 4 years ago. Direct link to mohamad's post “i have a question from pr...”
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?
Button navigates to signup pageButton navigates to signup page
(1 vote)
Answer
- Alex
  Posted 4 years ago. Direct link to Alex's post “An if/else statement will...”
  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.
  Comment on Alex's post “An if/else statement will...”
  (2 votes)
Anummujib
Posted 6 years ago. Direct link to Anummujib's post “What are the two diﬀerent...”
What are the two diﬀerent algorithms for a factorial problem?
Button navigates to signup pageButton navigates to signup page
(1 vote)
Answer
Anas Sallam
Posted 5 years ago. Direct link to Anas Sallam's post “The Russian dolls example...”
The Russian dolls example made things very clear from the beginning
Button navigates to signup pageButton navigates to signup page
(1 vote)
Answer
Piggy Backride
Posted 6 years ago. Direct link to Piggy Backride's post “"n! = (n+1)! / (n+1) n!=(...”
"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.
Button navigates to signup pageButton navigates to signup page
(1 vote)
Answer
- Jason Bit
  Posted 3 years ago. Direct link to Jason Bit's post “It's poorly laid out, but...”
  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.
  Comment on Jason Bit's post “It's poorly laid out, but...”
  (1 vote)
juhi sinha
Posted 5 years ago. Direct link to juhi sinha's post “how can i get previous no...”
how can i get previous node by coding in recursive method
Button navigates to signup pageComment on juhi sinha's post “how can i get previous no...”
(1 vote)
Answer

Computer science

Course: Computer science > Unit 1

Properties of recursive algorithms

Want to join the conversation?