Hello, everyone! The topic of Chapter 3 is Stack and Queue. 大家好。数据结构与算法这一讲的内容是
Today, we will talk about application of stack. 第三章，栈与队列。我们今天讲栈的应用。
Especially, mechanical transformation of recursion and optimized non-recursive function. 特别是，机械的递归转换以及优化以后的非递归函数。
We will introduce from following aspects, 我们会从以下几个方面来介绍
mechanical method. We start with setting a working stack. 机械的方法。首先是设置一个工作栈。
In the stack, we mainly stores 那这个栈里面呢，它主要的是保存
return address, some parameters and local variables. 返回的地址，还有一些参数以及局部变量。 然后是设置
Then we set t+i statements. In these statements, t+i 个语句。 这 t+i 个语句里面呢，
we assign numbers from 1 to t to every recursive statement. 我们从1 到 t 的编号是对应的原来 每一个递归的语句。
Label 0 is for the first executable statement. Actually, label 0 呢，是第一个可执行语句，实际上
it is a main entrance of recursive and a process of transformation. 也就是一个递归的总入口，一个 转换的过程。那，
Label t+1 is set in every ending of functions. label t+1 呢，它是设在每一个函数体的结束处，
That is, before function returns, we need to do some work. 也就是在递归返回到上一集的时候，需要做哪些工作。
Let us look at this non-recursive main entrance. 我们来看这个非递归的总入口。
We set an element in address t+1. 我们会设置一个 t+1
We see, 地址的 一个元素。我们再来看，
we use such a rule to replace every recursive statement. 每一个递归的语句，我们用这么一组规则来替换它。
Actually, we divide it into two parts. 那，实际上，以这个 label
The former part can be regarded as i 为界， 我们分成两个部分。前面其实可以看作是
a process of passing address of 一个函数调用的时候来保留这样的一些
some local variables stored when function is called. 局部变量啊，参数啊，然后传递这样的一个地址这么一个过程。
Then the statement, label i, that is, when the function returns, 然后，label i 这个语句呢，也就是说，当这个函数调用返回的时候，
then we push the result computed by the call 然后我们要把这些在这个底层调用里面，
to the stack. 计算出来的结果，那然后再推栈。
In every recursion exit, 那我们在每一个递归出口的地方，
we add a statement, goto label t+1. 要增加这个 goto label t+1 的一个语句。
This recursion exit, like this function ends, 这个递归出口呢，像这样的一个这边 整个这个函数结束，来像这边
and the statement f=n+1, they can return directly rather than recursion. f = n + 1， 这个也是不需要进行递归，可以直接上去返回。
These are recursion exits. Then, 那，这都是递归的出口的地方。然后呢，
we see the statement t+1. 我们来看这个标号为 t+1 的语句。
It is very easy. According to 那它其实很简单。就是根据我们的
the return address, 递归返回地址，然后
the goto statement jumps to the corresponding label that stands for every recursive statement. goto 跳转到相应的 label, 也就是我们刚才看到的每一条递归语句，
There is a set of rules. It passes values in 它都有一组规则。这个规则呢，在 label i
the positions of label i. That is, 的地方是做一些 这些值的一个传递，就是从
get the result computed by recursion and pass or compute them. 递归计算出来的结果，把它拿出来，然后再进行一些 值的传递和运算，这样的一些操作。
Especially, in the position of t+1, we actually meet the guard 那，特别是这样一个 t+1 的地方，那我们其实是遇到了刚才我们
we set in the bottom of stack at first. 最开始的时候，压在栈底的一个监视哨。
It indicates that the function has been executed completely. 表示整个这个函数处理呢，已经完成了。然后，
Then, you let the values in the stack be processed accordingly. 你把这个栈里面返回的这些值呢，作相应的处理。
We should export the recursions in loops. 对于循环里面的递归，我们要把它导出来，
In practise, we can use goto to rewrite loops. If there is nested recursive calls, 其实可以用goto 来改写循环。 那如果是有嵌套的递归调用，
like this form, we should peel it layer by layer. 像这种形式，那我们要把它一层层的剥出来，也就是说，
That is, process one recursive function for one statement, then 每一句语句呢，只处理一个递归函数，然后再
use the rules mentioned just now. 运用前面的规则来解决。
In the non-recursive transformation we have written, we see 对于我们已经写好的这么一个非递归的转换， 那我们看到里面带有
'goto' and some redundant push or pop. In addition, some local variables goto 还有可能其它的冗余的进栈出栈。另外有一些局部变量，
may be redundant, too. We analyse whether there is possibility of optimization. 可能也是有不必要的冗余，我们分析一下有没有优化的空间，好进行优化处理。
For this function, we consider, 那我们对这个函数，我们来看一下。
the working stack we designed consists of some parts. We can see 首先我们定义这个工作栈，会有哪几个部分。 那这个工作栈呢，可以看到这个是
this is return address of rd. And pn is a value parameter passed in, rd 返回地址， 然后 pn 呢就是一个传入的值差，
while pf is a return result of a function. pf 呢是一个计算的一个函数返回结果， q1,
In addition, q1 and q2 are local variables corresponding to q2 呢是相应于它的两次递归调用的这样的一个结构值作为
the two recursive calls. Then we examine the process of recursive call. 局部变量。然后我们看一下这个递归调用的过程。
Firstly, there is a main entrance. 那首先呢，是一个总的这个入口呢，
There is a guard in the bottom of stack at first. The return address is t+1. 一开始在栈底呢压一个监视哨， 让这个函数的返回地址呢是 t+1, 这里 t = 2,
Here t=2, so rd=3. Then we push it to stack. This label 0 is a 所以这个是 rd = 3。 然后我们把它压到栈底下。这个 label 0 呢是一个，
main entrance of non-recursion. Actually we can see if it is in recursive function, what step should be taken by the first statement. 整个非递归的总入口。实际上我们也可以看作在递归函数里面，我们 第一个这个语句，它应该进行什么处理。
At first we judge if n is less than 2. 那在这里我们首先判断， n 是不是小于 2。
If n is less than 2, it indicates that it can calculate directly. 如果是小于 2 呢，就表示 它是可以进行一个直接的求值运算。
Then we push the result into stack, because we can only use stack to pass the parameters. 然后我们把这个结果呢还要放到栈里面，因为我们只能通过栈来传递这些参数。
As it is actually a main exit of recursion, you can see 因为它实际上是一个递归的一个总的出口，你可以看到这里，它是一个出口，
here is a return of recursive function. So we add a statement, goto label 3. 是递归函数的一个返回的时候， 那我们要加一个goto
Then we examine the first recursive call. label 3 这样的语句。 然后我们看第一个递归调用的语句。
We firstly set the return address to 1. Then divide n by 2, 那我们首先呢把它的返回地址设为 1， 然后对 n 呢是除 2 ，
and push the value in the stack. 然后把这个值呢就是存到栈里面去。
Then we goto label 0 to do a overall scheduling. 然后我们就要 goto label0 去进行一个
Actually, 递归的这个总的一个分发的调度处理，那实际上我们，
when we call recursion, we can see 当我们递归调用的时候，我们也是可以看到，是
when it enters into bottom level of recursion, 在进入到底层深入进行递归的时候，
we can not get a real process and need to turn back to label 0 to dispatch. 那也是，我现在并不能够得到一个真正的处理，还是要 回到那个 label0
It is a LIFO operation, always going deep. 那儿，再去分发，它是一个 先进后出的一个操作，一直往底下深入。
If this is the first recursive statement 那 如果是这个第一个递归调用语句，
and the call is completed, 它在下面的这个调用处理已经都完了。
when it returns, we get the element 那它返回的时候，那我们就是从栈顶呢，
from the top of stack, then we consider where should this element pass to. 取出相应的元素，然后我们看这个值应该传到什么地方。
Because we got it from top of stack, exactly this layer, 因为我们是从栈顶取出来以后，那实际上呢，就是这个 这一层，它的
its q1 is return result of the left recursion. q1 也就是这个左边的这一次递归
It is actually the return value of 调用的这个返回结果。它就等于我们
our call for the deeper layer. Then we compute the value of q1. 这个深入的这一层调用呢，它返回的这个值。 然后我们求出这个
the value of q1, We push this value into the stack. q1 值， 我们就可以把这个元素呢又入到
The second recursive statement is similar. We should 栈里面。那第二个递归语句，它类似那我们要把
set the return address to 2. And there is goto label0. 这个返回地址呢，设成 2。而且这里是 goto label0 ，
If it is the second recursive statement, 那如果是第二个递归语句，
its corresponding down-layer process is completed. It returns to the position where 它相应的这个底层的处理已经完了。那返回到这个第二个递归语句的一个
machine processes the second recursive statement, that is , the operation of exiting stack. 机器处理的地方，也就是退栈的这个操作。 那我们就把
Then we take the corresponding element out from the working stack. 这个当前的工作栈里面的相应的元素呢取出来，那因为我们是
As it is the second recursive statement, we know the computed result 第二个递归调用语句，那我们知道我们刚才计算的结果呢，
is from right side. So in this situation, 是从右边来的，所以是，对应到这里面是，
it is the result of the second local variable. And, the f in this layer can be computed. 第二个局部变量的结果。而且呢，本层的这个 f 呢，它就可以计算了。就是它的 q1,
After q1, q2 are got and f is computed, we store the result into the stack. q2 都已经得到，那 f 的结果已经出来，然后我们再把这个结果存到栈里面去。
Thus, in the main exit of label3, 那，在这个， label3
we in practise judge which address it comes from, then 这样的一个 总的出口处理的地方，那我们其实就是判断
we go back to that address and continue to process. 刚才是从哪一个地址来的，然后我们就回到那个相应的地址，
Actually, it plays a role as an uniform processor. 去进行继续的处理，它实际上是做了一个统一的处理。
There is one thing special, if the return address is 3, in fact 那有一个特别的地方呢就是，如果返回地址是 3， 实际上是t
the position of t + 1, we have reached the guard, + 1 这样的一个地方，那我们已经碰到了压在栈底的那个监视哨，
indicating that the whole process of calculation is completed. 表示整个计算过程已经处理完了。
So the value of the function we computed 那我们所计算出来的这个函数的值，
is the final result. 就是我们整体的这一次处理的结果。
At last we return the value, done. 那我们把这个结果返回，那就处理完毕了。 对刚才的这样一个
For the transformation of non-recursion with goto statement, 带goto的一个非机械的转换的结果，
we can do some optimization. It consists of some parts. 我们可以进行优化。优化呢，主要是有几个部分。
Firstly, we can remove redundant operations of push and pop, and some 首先呢，就是消除冗余的进栈出栈， 还有就是消除一些
unnecessary local variables, 不必要的局部变量，特别是我们需要用
especially replacing the goto-structure with loop-structure. 循环的结构来代替那些带goto的那样的结构。
Let us analyse the process of recursion. Because it is a depth-first search, 那我们来分析一下它的这个递归调用的过程。因为我们其实是一个伸收的过程。
we can go deep along left branches until n < 2. 那我们是可以沿着这个左路一直降， 一直降到 n
Then we can compute the holistic value. 是小于 2 的时候，我们才可以计算整体的结果。
Therefore, it is different to retain a guard in the bottom of stack in this entrance. 因此呢，在这个入口的时候，保留这样一个栈底的监视哨，这还是一样。
Then we continue processing in a loop. 然后我们是一直做这样的一个循环处理。
Firstly, we push along left branch. If 那首先，我们是沿着左分支入栈， 如果是说
n >= 2, we continue pushing like this. And focus, rd = 1 as we come n 是大于等于2， 我就一直这样子入栈，而且呢，注意我们是从左边来的，
from left and n is divided by 2 before pushed into stack. 所以 rd 是等于 1 ， 而且 n 呢是比刚才那个除以 2
When it cannot be divided anymore, 再入到栈里面。 那出到不能够再左为止呢，
we know the result can be computed. 我们就知道，可以是计算出现在的结果。
We know, the result we have computed, 那我们计算这个结果呢，那我知道， 是 pf
pf can equal pn + 1, then we put the result 呢是可以等于pn + 1, 然后我们把这个结果
into the stack and wait for passing the parameters. 也是继续放在栈里面等着进行这些参数的传递。
If we returns from the second function, 那如果我们是从第二个
and we extend the tree deeply, we can see, 函数返回的，那如果我们把这个数画得更深一点，大家可以看到，
we can go up along the right branches when we returns from the second function. 从第二个函数返回的时候，我们一直可以从右路上升。
When it is going up, every time we process, 上升的过程中呢，我们每处理一次，那就是
it gets these valued computed from working stack. 得到这样的一个本程推出来的一些工作栈里面的这些数值。
And this return, 那这一次的这个返回呢，那我们可以看到 这个 pf，
we can see the pf we computed above, 我刚才退出来的这个值， 那，它就是我们从右边
it is the result we computed from right side. 计算出来的这样的右指数的一个f结果。
By multiplying it with q stored in stack, we can get the f-value of current node. 那跟刚才保存在栈里面的 q 相乘就得到了我当前这个接点
Then we push the computed result into the stack for further process. 它的 f 值。然后我们把计算结果还是入到栈里面继续处理。
If 如果是
its return value equals 1, 它的返回地址呢是等于 1 的情况，
we return from left side, 那我们就是从左边
and continue to process the index on the right side. 调用返回，那我们要继续进行右边的这个指数的处理。
We store the return result from left side 那我们就会从这个左边呢，
in the variable q, 调用出来的这个返回的结果， 把它存在这个
then enter the second recursion. q 隐式变量里面， 接着我们要
Just now we modify the value of return address to 2. 进入第二个递归。那我们把刚才这一层的这个值呢，
And divide n by 4. 我们要把它的返回地址修改为 2 ， 而且呢，把这个
Then push it to stack. n 呢 除以 4， 然后我们再压一层栈。
We continue this loop process, 那我们一直持续这样的一个循环的过程，
until we meet the element in the bottom of stack, that is 直到我们遇到栈底的那个元素，也就是 返回地址等于 3
the element which return address equals 3. Then the whole process completes, 的这个元素。 那整个的处理就结束，而且我们得到的这个栈底元素的
and we get the f value which is the return value of the element in the bottom of stack. 相应的函数返回值呢就是我们所需要的这个
We know the latest compiler can do a f 值。 那我们知道现在的编译系统，它对于
good job on processing recursion, and recursion is very easy end clear to learn. 递归的处理已经非常的高效，而且递归函数学起来呢非常的简单清晰
Then why do we need to consider the transformation from recursion to non-recursion? ，那我们为什么还需要研究一下这样的递归到非递归的转换呢。
Firstly, saying from the aspect of our teaching objectives, we mainly want to 首先，从我们教学的目标来说呢，主要是让大家深入的理解
let you understand the working principle of recursion. 这样的一个递归调用的工作原理。
Otherwise, saying form expense of space and time, it is also valuable. 另外呢，从我们的时间和空间的开销上来说，它也是有意义的。
Let us consider thus test case. 那我们看这样的一个测试环境。
For the recursive program of quick sort, 对于快速排序这样一个递归程序，
we can simply write a recursive version, 那如果我们就是简单的写成一个 递归的快排，然后还有对应到
or we can write a non-recursive version using STL 里面的 这个排序，另外呢就是我们相应的，
mechanical transformation from recursion to non-recursion. 自己写的机械方法的非递归和优化以后的非递归。
We will see, the latter is more efficient, in all situations. 那可以看到，还是我们自己编写的算法是更加的高效。在各种情况下都是这样。
On the other hand, as for efficiency of space, 那，另外，从空间效率来说，
because our recursive functions need to use working stack of compiler, 因为我们递归函数它需要用到编译系统的工作栈，
and the compiler is limited, 那编译的这个堆栈呢，它是比较有限的。
especially in its space. 特别是它的栈的空间是非常受限制的。
For a recursive function, in default setting, 那对于这么一个递归的函数， 那在默认的设置下，当
when x exceeds 10 thousand, the stack would overflow. x 超过了一万多的时候，就会出现堆栈的溢出。
But if we write it in the form of nun-recursion, 而如果我们把它写成非递归的形式，
the number of elements in stack can 那，栈里面的元素呢，它就可以
be more. Actually, only when x is more than 更多，那实际上也就是说，当这个 x
30 million, errors may occur. We can see the 超过 三千多万的时候呢，才会出现错误。那我们可以看到
the comparison of space is astonishing. 这两个空间的对比是非常惊人的。也就是说，
In other words, if we write non-recursive function , we can handle much bigger data, 我们如果自己编写非递归的函数， 我们可以处理更大规模的数据，
by using a bigger stack. 可以来使用一个更大规模的栈。
Finally, we consider a question. 那我们最后给大家留一下思考。
We have learnt to use mechanical transformation methods to write programs of factorial, 也就是用机械的转换方法来编写阶乘的函数，
Fibonacci sequence and Hanoi. Note that, why do we use 还有2阶的斐波那契数列以及河内塔。那特别要注意我们这里为什么
mechanical methods? Because through the process of mechanical methods, 强调机械的方法呢？因为我们掌握那一套机械方法的过程，
we can understand the working principle of recursion deeply. 是能够更加深入的理解这样的一个递归的工作原理。
After being on top of it, you can optimize it yourself. Than you! 你熟练的掌握了以后呢再去优化它就可以了。谢谢大家。