1.1. 2.1 Recursion

Have you ever seen a set of Russian dolls? At first, you see just one figurine, usually painted wood, that looks something like this:

You can remove the top half of the first doll, and what do you see inside? Another, slightly smaller, Russian doll!

You can remove that doll and separate its top and bottom halves. And you see yet another, even smaller, doll:

And once more:

And you can keep going. Eventually you find the teeniest Russian doll. It is just one piece, and so it does not open:

We started with one big Russian doll, and we saw smaller and smaller Russian dolls, until we saw one that was so small that it could not contain another.

What do Russian dolls have to do with algorithms? Just as one Russian doll has within it a smaller Russian doll, which has an even smaller Russian doll within it, all the way down to a tiny Russian doll that is too small to contain another, we'll see how to design an algorithm to solve a problem by solving a smaller instance of the same problem, unless the problem is so small that we can just solve it directly. We call this technique recursion.

Recursion has many, many applications. In this module, we'll see how to use recursion to compute the factorial function, to determine whether a word is a palindrome, to compute powers of a number, to draw a type of fractal, and to solve the ancient Towers of Hanoi problem. Later modules will use recursion to solve other problems, including sorting.

1.2. The factorial function

For our first example of recursion, let's look at how to compute the factorial function. We indicate the factorial of $n$ by $n!$ . It's just the product of the integers 1 through $n$ . For example, $\begin{matrix} 5! = 1 \times 2 \times 3 \times 4 \times 5 = 120 \\ (1) \end{matrix}$ You might wonder why we would possibly care about the factorial function. It's very useful for when we're trying to count how many different orders there are for things or how many different ways we can combine things. For example, how many different ways can we arrange $n$ things? We have $n$ choices for the first thing. For each of these $n$ choices, we are left with $n - 1$ choices for the second thing, so that we have $n (n - 1)$ choices for the first two things, in order. Now, for each of these first two choices, we have $n - 2$ choices for the third thing, giving us $n \cdot (n - 1) \cdot (n - 2)$ choices for the first three things, in order. And so on, until we get down to just two things remaining, and then just one thing remaining. Altogether, we have $n \cdot (n - 1) \cdot (n - 2) \cdot . . . \cdot 2 \cdot 1$ ways that we can order $n$ things. And that product is just $n!$ ( $n$ factorial), but with the product written going from $n$ down to 1 rather than from 1 up to $n$ .

Another use for the factorial function is to count how many ways you can choose things from a collection of things. For example, suppose you are going on a trip and you want to choose which T-shirts to take. Let's say that you own $n$ T-shirts but you have room to pack only $k$ of them. How many different ways can you choose $k$ T-shirts from a collection of $n$ T-shirts? The answer (which we won't try to justify here) turns out to be $n! / (k! \cdot (n - k)!) k$ . So the factorial function can be pretty useful. You can learn more about permutations and combinations here, but you don't need to understand them to implement a factorial algorithm.

The factorial function is defined for all positive integers, along with 0. What value should 0! have? It's the product of all integers greater than or equal to 1 and less than or equal to 0. But there are no such integers. Therefore, we define 0! to equal the identity for multiplication, which is 1. (Defining 0! = 1 meshes nicely with the formula for choosing $n$ things out of $n$ things. Suppose that we want to know how many ways there are to choose $n$ things out of $n$ things. That's easy, because there is only one way: choose all $n$ things. So now we know that, using our formula, $n! / (n! \cdot (n - n)!)$ should equal 1. But $(n - n)!$ is 0!, so now we know that $n!$ should equal 1. If we cancel out the $n!$ in both the numerator and denominator, we see that $1 / (0)!$ should equal 1, and it does because 0! equals 1.)

So now we have a way to think about $n!$ . It equals 1 when $n = 0$ , and it equals $1 \cdot 2 \cdot . . . \cdot (n - 1) \cdot n$ when $n$ is positive.

1.3. Challenge: Iterative factorial

Finish the provided factorial function, so that it returns the value n!. Your code should use a for loop to compute the product 1 2 3 ... n. If you write the code carefully, you won't need a special case for when n equals 0.

Once implemented, uncomment the Program.assertEqual() statements at the bottom to verify that the test assertions pass.

var factorial = function(n) {
    var result = 1;


    return result;
};

println("The value of 5! should be " + 5*4*3*2*1);
println("The value of 5! is " + factorial(5));
println("The value of 0! should be 1");
println("The value of 0! is " + factorial(0));

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

1.4. Recursive factorial

For positive values of n, let's write n! as we did before, as a product ofnumbers starting from n and going down to 1: n!=n·(n- 1)...2 . 1. Butnotice that (n-1)...2 .1 is another way of writing (n- 1)!, and so we can saythat n!=n·(n- 1)!. Did you see what we just did? We wrote n! as a productin which one of the factors is (n- 1)!. We said that you can compute n! bycomputing(n-1)! and then multiplying the result of computing (n - 1)! by n.You can compute the factorial function on n by frst computing the factorialfunction on n-1. We say that computing (n- 1)! is a subproblem that wesolve to compute n!.

Let's look at an example: computing 5!

You can compute 5! as 5 .4!.
Now you need to solve the subproblem of computing 4!, which you can compute as 4 . 3!.
Now you need to solve the subproblem of computing 3., which is 3 . 2!
Now 2!, which is 2 . 1!.
Now you need to compute 1!. You could say that 1! equals 1, because it'sthe product of all the integers from 1 through 1. Or you can apply theformula that 1!= 1 .0!. Let's do it by applying the formula.
We defined 0! to equal 1.
Now you can compute 1!=1.0!= 1.
Having computed 1!= 1, you can compute 2!=2.1!= 2.
Having computed 2!=2,you can compute 3!=3.2!= 6.
Having computed 3!=6, you can compute 4!=4.3!= 24.Finally, having computed 4!=24, you can fnish up by computing5!=5.4!= 120.

So now we have another way of thinking about how to compute the value ofn!, for all nonnegative integers n:

lf n=0, then declare that n!= 1.
Otherwise,n must be positive. Solve the subproblem of computing(n- 1)!, multiply this result by n, and declare n! equal to the result of this product.

When we're computing n! in this way, we call the frst case, where weimmediately know the answer, the base case, and we call the second case.where we have to compute the same function but on a different value, therecursive case.

1.5. Challenge: Recursive factorial

Base case In this challenge you will write a recursive function that returns the value of n!.

Start by writing the base case: if n is zero, then factorial should just return the value 1.

Once implemented, uncomment the Program.assertEqual() for factorial(0) at the bottom to verify that the test assertion passes.

var factorial = function(n) {
    // base case: 

    // recursive case:
}; 

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

1.6. 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 originalproblem) by solving the subproblem of computing the factorial of a smallernumber, that is, computing (n-1)! (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 musteventually arrive at the base case. When computing n!, the subproblems getsmaller 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 numberusing our recursive method? To compute (-1)!, you would frst try to compute(-2)!, so that you could multiply the result by -1. But to compute (-2)!, youwould frst try to compute (-3)!, so that you could multiply the result by -2.And then you would try to compute (-3)!, and so on. Sure, the numbers aregetting smaller, but they're also getting farther and farther away from the basecase 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 getinto trouble if you don't make the subproblems progressively smaller. Here's anexample. Let's take the formula n!=n·(n- 1)! and divide both sides by n,givingn!/n=(n- 1)!. Let's make a new variable, m, and set it equal to n + 1.Since our formula applies to any positive number, let's substitute m for n,giving m!/m=(m-1)!.Since m=n+ 1, we now have(n+1)!/(n+1)=(n+1-1)!.Switching sides and noting thatn+1-1=ngives us n!=(n+ 1)!/(n+ 1). This formula leads us to believe that you cancompute n! by frst computing (n + 1)! and then dividing the result by n + 1But to compute (n+ 1)!, you would have to compute (n + 2)!, then (n + 3)!,and so on. You would never get to the base case of 0. Why not? Because eachrecursive subproblem asks you to compute the value of a larger number, not asmaller number. lf 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 solvedwithout further recursion.

Let's go back to the Russian dolls. Although they don't fgure into anyalgorithms, you can see that each doll encloses all the smaller dolls (analogousto the recursive case), until the smallest doll that does not enclose any others(like the base case)

2.1 递归调用