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.

Q: "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.

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.

Question 1

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

Accepted Answer

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

Question 2

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.

Accepted Answer

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

Question 3

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

Accepted Answer

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

Question 4

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?

Accepted Answer

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!

Question 5

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?

Accepted Answer

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.

Question 6

"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.

Accepted Answer

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.

Question 7

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

Accepted Answer

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

Course: Computer science theory > Unit 1

Properties of recursive algorithms

Want to join the conversation?