We might have all heard the game of Guess the Number. Sorry, it's the Tower of Hanoi. Let's look at a simplified version of Tower of Hanoi first. Keep 4 disks constantly in the state of bigger disks below smaller ones. A disk is moved from the first rod to the third rod through the second rod. We may see that, we may let another person to move the 3 smaller disks, as required, to the second rod via the third rod, and we move the biggest disk to the third rod. Then, let another person move the 3 smaller disks from the second rod to the third rod through the first rod. He may find a third person to help him move the 2 smaller disks, and he moves the biggest disk (of the three) by himself. Similarly, this task can be finished. We feel that this question has no obvious loop solution, but there seems to exist a unique way to solve it. What is this? It's recursion. Recursion is among those typically showing computational thinking. We'll use the example of generating the nth Fibonacci Sequence to illustrate the concept of recursion. Let's first look at the way of realizing the loop of the nth Fibonacci Sequence. We know, as for the Fibonacci Sequence, its form is like this-- the first element is 0, the second is 1, each subsequent number is the sum of the previous two. So, it is a sequence like this. It is simple in looping. Initial values a and b are well defined, then updated repeatedly, assigning b to a and assigning a+b to b continuously, finally outputting the value of a. Well, how can we achieve this with the thought of recursion. As we know, when the value is 0 or 1, we return its original value. Subsequently, this item is f(n), for example. Is it the sum of f(n-2) and f(n-1), A recursion program is written like this? A recursion program is written like this. When n equals 0 or q, return n, else return f(n-1)+f(n-2). We see here are the recursion codes more concise and easier for understanding. It conforms to our natural logic. When writing a recursion program, pay special attention to two points. First, it must have a condition for stopping recursion, that is to say, it should have an outlet of recursion. Here, as we may notice, when n is 0 or 1, we return n, which is its outlet. Besides, the repeatedly called one is its copy of original content, which is simpler than the original one. It's not allowed to write here like f(n) + f(n), in which it would not return. Let's briefly look at the process of execution of this program. For instance to compute the 5th element, i.e. to compute f(4), f(4) return f(3)+f(2), while for f(3), it returns f(2)+f(1), for f(2), it returns f(1)+f(0). Actually, at this branch, there is already a result, since f(1) may return 1, and f(0) may return 0. It's similar for others. When it comes to the position of "return 1" or "0", some parts of regression have already finished. It allowed returns upwards one level by one level. This is actually a process of recursion. After each value returns upwards, we can finally compute the value of f(4), which is a process of recursio. Let's ask you a question. Let guess, (In the same program) whose execution efficiency is higher, recursion or loop? I suppose most of you may say it's recursion, since it looks very concise. Actually, the execution efficiency of recursion is not high. It consumes more system resources than loops. Since it calls one level after another inwards, and upon completion, returns one level after another, its execution efficiency is not high. Then, why do we still use recursion? Because there are some questions, for which we can not find obvious loop solutions, but there are obvious recursion solutions, for example, the famous Tower of Hanoi puzzle. Tower of Hanoi originates from an India myth. Since it is quite complex. I'll directly show you the program. Let's understand it. Suppose there are four disks. The result of program is to output the entire movement process. The function has four arguments. The first three arguments, represent the uppermost disk of a certain rod. For example, for such an output, it represents taking away a disk from the rod "a". Which one? and moving the uppermost disk to "c". Let's look at the program. When there is more than one disk, can we consider it like this? As for all the disks on the rod "a", we may move the n-1 one(s) in it, to "b" via "c". For example, suppose this is its n-1 disk(s), this is the biggest disk at the bottommost. We may move it to "b" via "c". Can we directly move another disk? Directly move from "a" to "c". So, here, as we see, the function can be written like this. How many are moved? from "a" to "b" via "c". There are n-1 disks. The next step is from "a" to "c", to take one disk. What's next? Should we move the n-1 disk(s) from "b" to "c" via "a"? So, let's see where the outlet of the problem of moving from "c" via "a" is? When n equals 1, i.e. only one disk remains, can we do it like this? Directly move from "a" to "c". Thus, if there are 4 disks, the last movement process is like this. I'll leave the movement processes of 3 disks to you as an assignment. We may also consider this, how many steps are needed for n disks?