Hello everyone, Data Structure and Algorithm 大家好，数据结构与算法， comes to Chapter 3, Stack and Queue. 这一讲的内容是， 第三章，栈与队列。 Especially application of stack, and transformation from recursion to non-recursion. 特别是栈的应用，递归到非递归的转换。 In this chapter, we firstly introduce 那这一讲呢，我们首先介绍 the principle of recursive function. Transformation of recursion well be introduced in the next chapter. 递归函数的调用原理。后面一讲会介绍， 递归的转换方法。 Let us look at the process of a recursion. In such a function, 那我们来看一下，递归的这个过程。对于这么一个阶层函数， we can see that it has a recursion exit and a recursion regular. 我们可以看到，它主要是有递归出口，然后还有， The recursion regular transform the problem to smaller sub-problems. 递归规则。这个递归规则呢，它是把这个问题化成规模更小的子问题。 And, it it towards the recursion exit. 而且呢，是向递归出口逼近。
那如果对这个阶层 It is easy to use non-recursion method to implement this function. Actually, it is just a loop.
的函数，我们用非递归的方法，是很容易编算法来实现的。
它实际上就是个一层循环。 But how about more complex problem, such as Hanoi? Let us loop at the example of Hanoi. 但是对于河内塔那样的比较复杂的问题呢，那我们来看一下河内塔问题的例子。 This problem is frequently used as an example of recursion in the introductory courses of program design language. 那，这个河内塔问题呢，也是我们在 程序设计语言的入门课程里面经常用到的一个递归例子。 There are n plates, and three pillars, one of which is source pillar, 有这么一个问题，就是，有n个盘子，然后有 and the other two are target pillar and middle pillar respectively. 3个柱子，其中一个是起始，一个是目标，一个是中间柱。 We start with the source pillar, 那我们从起始的柱子出发，我们要挪动这个 moving plates from it to the target pillar. 碟子，然后把它们都挪到这个目标柱。 In the process of moving plates, any plates can never be put onto a smaller plate. 在挪动的过程中呢，都不允许大盘子压在小盘子之上。 It is easy to solve small-scale cases, such as the case of two plates, in which we can move plates naturally. 那对于小问题规模，我们很容易做，比如说只有两个盘子的情况，我们很容易就移过去了。 In big-scale cases, that is, n >= 3, 那对于问题比较大规模的情况，或者是说， we need to consider carefully. Let us look at the recursive function. 甚至对于n等于3个以上，就是需要我们来思考了。
让我们来看一下，它的这个， If we can reduce the problem scale by one, 递归函数的写法。那如果是说，我们如果能够把 because we know, it is easy to handle the case of n = 1 or 2. 问题规模缩小一个，因为我们知道，对于n等于1，等于2，很容易做。 Thus, we reduce the problem scale by one, 那么如果我把这个问题规模缩小一个，然后呢，我们把这个它的 and do some transformation among the source pillar, 起始，然后还有是，它的 middle pillar and target pillar. 目标，还有它的这个，中间的过渡的柱子，我们给它进行一些转换， Like this, we reduce the scale by one, 那如果比如说我们这一个，把n的规模缩小1， and remain the source pillar, 然后呢我们把这个起始的是不变， and exchange the target pillar with the middle pillar. 我们的这个目标呢，我现在把它变成原来的中间过渡的， Suppose we can solve the (n-1)-scale problem, 然后呢，原来的这个目标呢作为中间过渡的这样的一个。就假设我如果能够解决 we move the (n-1) plates to the target pillar. n减1规模的这个问题，那就搬过去了。那后面呢，也是类似就是，我们 After that, we move the biggest plate to the target pillar, 把这个n减1个盘子成功的搬过去以后，那我这个最大的那个盘子， from X. 就可以从这个x能够搬到这个目标的塔。 We can move the remaining part by the same method as mentioned above. 然后剩下的这个呢，就是说，我们按照刚才的方法，只是说这些柱子 The only difference is the pillars. This is a classic process of recursion. 不一样，我就可以同样的搬过去。那这是个非常经典的递归的过程。 We can regard a computer program or a piece of function code 那我们对于一个计算机的程序，或者是说其中的某一段 as a black box. The black box can realise certain functions. 函数，其实我们都可以看作是一个黑匣子。这个黑匣子呢，它是完成一定的功能， Every input maps an output. Thus, 然后对这个，输入呢，映射到一个输出，因此呢， we suppose it is a H machine to solve the problem of Hanoi. 我们就假设它是一个H机，来解决河内塔问题。 There are some parameters, passing by 那中间它有些这个参数，那这些参数的传递呢， the inner stack. 是要通过这个内部栈来进行的。 Let us look at its process of transformation. In this case, 那我们来看它的，这样的一个转换过程。实际上，这个是对于 the problem scale n equals 3. It can be divided to two smaller sub-problems. 问题规模n等于3的时候，它分解成两个更小的子问题。 Thus, each sub-problem can be also divided to two smaller sub-sub-problem, 那么，每一个这个小的子问题呢，它又是分解为两个更小的子问题，所以这就是一个递归的 so it is a recursive function. Actually, we can implement this recursive function 调用数。那这个递归调用数呢，实际上，我们就可以用一个中序变例 by inorder traversal. Of course, we use different traversal method to solve different problems. 的方法来实现。
当然是对不同的问题，我们的变例方法是不一样的。 For the problem of Hanoi, because the step of moving the biggest plate 在河内塔这个问题里面，因为它中间移动盘子的这个过程， is between two recursion functions, we 它是在这两个递归函数之间，因此呢， use the inorder traversal to implement it. 它这个过程的话，实际上就是一个中序变例。 As we saw just now, its process of recursion calling, 那我们刚才看到，它的这些递归调用的这个过程。 it is through inorder traversal. It is 那它是，经过中序变例，它也是一个 a depth-first search. In other words, Last In First Out, to get such a result, 伸收，也就是说，后进先出，最后得到这样一个结果。 is to solve the whole problem of Hanoi. 就是完成了整个对于这个河内塔问题的一个求解。 Let us look at the process of passing parameters in the recursion stack. 那我们看一下，这个参数在 递归栈里面的，这是传递的过程。那可以看到， We can see, when we call the next level sub-problem, the current level should be stored here. 我们在调用下一级的这个子问题的时候，上一级要保存在这， Then in the next level, its scale is smaller. The parameters are passing constantly. 然后下一级的这个，子问题它的规模缩小，然后这些参数呢， 不断地进行这个传递。 Look at a formula of recursion. 那我们再来看一个递归的数学公式。 There is a return value in this formula. Using this problem, 这个公式呢，它就是有返回值。那用这个问题呢， we discuss the process of passing recursion parameters. 我们来研究一下，这个递归的参数传递的过程。 The recursive function is easy to write out. 那它的这个递归函数很容易就写出来了，是非常简单的。 For the convenience of processing, we put the return value here as a reference-type value parameter. 那为了处理的方便，我们把它的返回值呢，作为一个引用型的值参， As adding this reference-type value parameter, we need to define some local variables. 放在这。因为多了这个引用型的值参，所以我们也需要定义几个内部的局部变量。 Then, the equal procedure is written out. 然后呢，这个等价过程写出来了。 After we write this function, we consider the executing process. 那我们写出这个函数以后，再来看一下，它的一个执行的这个过程。 Firstly, we look at the dynamic allocation of storage when function running. 那在看这个执行过程之前，我们首先 Pay attention to that there is code area, 看一下这个函数运行的动态存储分配，其中特别要注意的就是， followed by global static area. Otherwise, stack and heap need to be noted. 有代码区，然后，全局的静态区。另外有两个特别注意的就是栈和堆。 The stack is for compilation, which has a limited space. 那这个栈呢，是编译栈的空间。编译栈的空间是非常有限的， Its main function is to allocate some small temporary variables. 而且它主要是用来分配一些比较小的临时变量， It is suit for the Last In First Out data structures. 它适合分配那种后进先出的这样的数据结构。 For example, function calling uses this stack frequently. 那例如，函数调用就是大量的要用到这个栈。 However, heap is usually used in non-FIFO cases. 而堆呢主要是对于一些不符合LIFO的， Such data structures, especially spaces for pointers, are allocated in heap. 这样的一些数据结构，特别是像指针这样的空间，那都是在堆里面去分配的。 Let us look at calling steps of recursive function. 那我们再来看一下递归函数的调用步骤。那么，递归函数 It is similar with calling steps of ordinary functions. 的调用步骤，它其实跟普通的函数调用步骤也是类似的。 It is mainly divided into two parts, calling and return. 那我们主要分为，调用和返回这两个部分。 That is, when we call a function, we reach a calling point. 就是说，当我们要调用一个函数的时候，在这个点，我们是一个调用点， At this point, we need to store our information, 在调用点的时候，我们会需要保存我们现在的这个信息， including parameters and return address. 包括参数，还有就是，我这个调用点，自己的返回地址。 Then we allocate some data area, which is in stack. 然后呢我分配一些数据区，这个是在栈里面分配的。 Then we transfer control to the function 然后就把这个控制呢，转移到它的这个 that is called. 被调的这个下一级函数。 Before return, it need to store some information of parameters. 在返回之前，它首先需要保存一些参数的信息。 Then, release data space in stack. The control is 然后呢，是释放这个在栈里面的数据空间。然后它把这个 transferred back to the caller. It should execute from the calling point. 控制权又返回到它的主调函数，回到这个断点，再继续执行。 Through the analysis of the recursive function, 那刚才这个递归函数， we can conclude that it is a 它的一个分解，我们就可以看到，它是一个 process of LIFO, that is, we divide the problem until 后进先出的这样一个过程，也就是，我们一直分解到 we meet recursion exit. Then we calculate the value and return. 递归出口，然后这个值算出来，再返回到上一层，然后再看， We continue to call the second recursive function. After two results are both worked out, we return to the upper level. 他继续这个第二个递归调用，然后这两个结果都出来，再返回到上一层执行。 Well, through the process of executing in stack we can see that for this function we set a guard.
好，那看它的栈里面的这个执行的过程我们也可以看出来呢，
对于这个函数，那首先呢，我们要放一个监视哨， The guard is a final exit. 这个监视哨呢，是一个 That is, when it finished, the function has completed. 递归的总出口。也就是说，当它出来的时候，这个函数整体就完成了。 Then, this rd1 is the first recursive call on the left. 然后呢，这个 rd1，rd2呢，是左边那个第一个 This rd2 is the second recursive call on the right. 递归调用语句，rd2呢，是右边这第二个递归调用语句。 Correspondingly, there are some parameters. For example, when executing this level, 然后相应的有些参数。那比如说在 用到这一层的时候， we can see, it can get the value of the function, 2. Then, it should clear data space in this level and pass this value to the upper level.
那我们可以看到，因为是已经到了递归出口这一块，然后它能够计算出，这个函数值是2。
然后呢，它把这个，这层的数据区域， 给它退掉，把这个值呢要传回到上一层。 In the upper level, it continue to call the second recursive call and execute it. 然后上一层呢，它是继续 要进到他的第二个递归调用语句，再去 So that is the process of passing parameters. 执行。所以这就是一个，参数传递的这样一个过程。 Let us consider that for these two functions, 那我们思考一下，对于这两个函数， factorial and Fibonacci Sequence, 就是阶层和2阶的斐波那契数列， please draw the number of recursive calls and the process of using stack to simulate recursion 请画出n等于4的情况下，它们的递归调用数以及 in the case of n=4. Thank you. 我们用栈来模拟整个递归调用的执行过程。谢谢大家。
