CS interview 经验

       总结： 一为知识， 二为实践， 三为目标， 四为心态， 五为技巧

1. CS入门课：建立CS思维过程

           Structure and Interpretation of computer programming: 
           http://www.youtube.com/playlist?list=PL3E89002AA9B9879E


2. 训练：方法就是刷题 重在思考总结归纳
              入门课程-----目的是获取最全面的CS知识。参考www.programmerinterview.com
              进阶-----深入学习 a.数据结构 b.算法 c.数据库 d.操作系统
3. 实践：自己写code, build自己的作品。主要把手头的project写出来。
4. 明确目标

      
         
     


     

转载-递归算法详解（二）

转载http://www.cnblogs.com/zhangqqqf/archive/2008/09/12/1289730.html

递归最重要的是步骤是：
1.找递归出口（也就是递归的结束条件，一般用return 返回）。
2.找出递归到最后一层时，需要进行的操作函数（实际上就是需要重复进行的运算）。

这里有一个简单的程序，可用于说明递归。程序的目的是把一个整数从二进制形式转换为可打印的字符形式。例如：给出一个值4267，我们需要依次产生字符‘4’，‘2’，‘6’，和‘7’。就如在printf函数中使用了%d格式码，它就会执行类似处理。

     我们采用的策略是把这个值反复除以10，并打印各个余数。例如，4267除10的余数是7，但是我们不能直接打印这个余数。我们需要打印的是机器字符集中表示数字‘7’的值。在ASCII码中，字符‘7’的值是55，所以我们需要在余数上加上48来获得正确的字符，但是，使用字符常量而不是整型常量可以提高程序的可移植性。‘0’的ASCII码是48，所以我们用余数加上‘0’，所以有下面的关系：

          ‘0’+ 0 =‘0’
          ‘0’+ 1 =‘1’
          ‘0’+ 2 =‘2’
      　　　    ...

　　从这些关系中，我们很容易看出在余数上加上‘0’就可以产生对应字符的代码。接着就打印出余数。下一步再取商的值，4267/10等于426。然后用这个值重复上述步骤。

　　这种处理方法存在的唯一问题是它产生的数字次序正好相反，它们是逆向打印的。所以在我们的程序中使用递归来修正这个问题。

　　我们这个程序中的函数是递归性质的,因为它包含了一个对自身的调用。乍一看，函数似乎永远不会终止。当函数调用时，它将调用自身，第2次调用还将调用自身，以此类推，似乎永远调用下去。这也是我们在刚接触递归时最想不明白的事情。但是，事实上并不会出现这种情况。

　　这个程序的递归实现了某种类型的螺旋状while循环。while循环在循环体每次执行时必须取得某种进展，逐步迫近循环终止条件。递归函数也是如此，它在每次递归调用后必须越来越接近某种限制条件。当递归函数符合这个限制条件时，它便不在调用自身。

在程序中，递归函数的限制条件就是变量quotient为零。在每次递归调用之前，我们都把quotient除以10，所以每递归调用一次，它的值就越来越接近零。当它最终变成零时，递归便告终止。

/*接受一个整型值（无符号0，把它转换为字符并打印它，前导零被删除*/

#include <stdio.h>

int binary_to_ascii( unsigned int value)
{          unsigned int quotient;
  
   　　quotient = value / 10;
   　　if( quotient != 0)
       　　　　binary_to_ascii( quotient);
   　　putchar ( value % 10 + '0' );
}

递归是如何帮助我们以正确的顺序打印这些字符呢？下面是这个函数的工作流程。
       1. 将参数值除以10
       2. 如果quotient的值为非零，调用binary-to-ascii打印quotient当前值的各位数字

　　3. 接着，打印步骤1中除法运算的余数

　　注意在第2个步骤中，我们需要打印的是quotient当前值的各位数字。我们所面临的问题和最初的问题完全相同，只是变量quotient的值变小了。我们用刚刚编写的函数（把整数转换为各个数字字符并打印出来）来解决这个问题。由于quotient的值越来越小，所以递归最终会终止。

　　一旦你理解了递归，阅读递归函数最容易的方法不是纠缠于它的执行过程，而是相信递归函数会顺利完成它的任务。如果你的每个步骤正确无误，你的限制条件设置正确，并且每次调用之后更接近限制条件，递归函数总是能正确的完成任务。

　　但是，为了理解递归的工作原理，你需要追踪递归调用的执行过程，所以让我们来进行这项工作。追踪一个递归函数的执行过程的关键是理解函数中所声明的变量是如何存储的。当函数被调用时，它的变量的空间是创建于运行时堆栈上的。以前调用的函数的变量扔保留在堆栈上，但他们被新函数的变量所掩盖，因此是不能被访问的。

　　当递归函数调用自身时，情况于是如此。每进行一次新的调用，都将创建一批变量，他们将掩盖递归函数前一次调用所创建的变量。当我追踪一个递归函数的执行过程时，必须把分数不同次调用的变量区分开来，以避免混淆。

　　程序中的函数有两个变量：参数value和局部变量quotient。下面的一些图显示了堆栈的状态，当前可以访问的变量位于栈顶。所有其他调用的变量饰以灰色的阴影，表示他们不能被当前正在执行的函数访问。

假定我们以4267这个值调用递归函数。当函数刚开始执行时，堆栈的内容如下图所示： 

执行除法之后，堆栈的内容如下：

  
接着，if语句判断出quotient的值非零，所以对该函数执行递归调用。当这个函数第二次被调用之初，堆栈的内容如下：

堆栈上创建了一批新的变量，隐藏了前面的那批变量，除非当前这次递归调用返回，否则他们是不能被访问的。再次执行除法运算之后，堆栈的内容如下：

quotient的值现在为42，仍然非零，所以需要继续执行递归调用，并再创建一批变量。在执行完这次调用的出发运算之后，堆栈的内容如下：

此时，quotient的值还是非零，仍然需要执行递归调用。在执行除法运算之后，堆栈的内容如下：

　　不算递归调用语句本身，到目前为止所执行的语句只是除法运算以及对quotient的值进行测试。由于递归调用这些语句重复执行，所以它的效果类似循环：当quotient的值非零时，把它的值作为初始值重新开始循环。但是，递归调用将会保存一些信息（这点与循环不同），也就好是保存在堆栈中的变量值。这些信息很快就会变得非常重要。

　　现在quotient的值变成了零，递归函数便不再调用自身，而是开始打印输出。然后函数返回，并开始销毁堆栈上的变量值。

每次调用putchar得到变量value的最后一个数字，方法是对value进行模10取余运算，其结果是一个0到9之间的整数。把它与字符常量‘0’相加，其结果便是对应于这个数字的ASCII字符，然后把这个字符打印出来。 

   输出4：

接着函数返回，它的变量从堆栈中销毁。接着，递归函数的前一次调用重新继续执行，她所使用的是自己的变量，他们现在位于堆栈的顶部。因为它的value值是42，所以调用putchar后打印出来的数字是2。

  输出42：

接着递归函数的这次调用也返回，它的变量也被销毁，此时位于堆栈顶部的是递归函数再前一次调用的变量。递归调用从这个位置继续执行，这次打印的数字是6。在这次调用返回之前，堆栈的内容如下：

  输出426：

现在我们已经展开了整个递归过程，并回到该函数最初的调用。这次调用打印出数字7，也就是它的value参数除10的余数。

  输出4267：

然后，这个递归函数就彻底返回到其他函数调用它的地点。
如果你把打印出来的字符一个接一个排在一起，出现在打印机或屏幕上，你将看到正确的值：4267

汉诺塔问题递归算法分析：

　　一个庙里有三个柱子，第一个有64个盘子，从上往下盘子越来越大。要求庙里的老和尚把这64个盘子全部移动到第三个柱子上。移动的时候始终只能小盘子压着大盘子。而且每次只能移动一个。

　　1、此时老和尚（后面我们叫他第一个和尚）觉得很难，所以他想：要是有一个人能把前63个盘子先移动到第二个柱子上，我再把最后一个盘子直接移动到第三个柱子，再让那个人把刚才的前63个盘子从第二个柱子上移动到第三个柱子上，我的任务就完成了，简单。所以他找了比他年轻的和尚（后面我们叫他第二个和尚），命令：

          ① 你丫把前63个盘子移动到第二柱子上

          ② 然后我自己把第64个盘子移动到第三个柱子上后 

          ③ 你把前63个盘子移动到第三柱子上 

      2、第二个和尚接了任务，也觉得很难，所以他也和第一个和尚一样想：要是有一个人能把前62个盘子先移动到第三个柱子上，我再把最后一个盘子直接移动到第二个柱子，再让那个人把刚才的前62个盘子从第三个柱子上移动到第三个柱子上，我的任务就完成了，简单。所以他也找了比他年轻的和尚（后面我们叫他第三和尚），命令： 

          ① 你把前62个盘子移动到第三柱子上 

          ② 然后我自己把第63个盘子移动到第二个柱子上后 

          ③ 你把前62个盘子移动到第二柱子上 

　　3、第三个和尚接了任务，又把移动前61个盘子的任务依葫芦话瓢的交给了第四个和尚，等等递推下去，直到把任务交给了第64个和尚为止（估计第64个和尚很郁闷，没机会也命令下别人，因为到他这里盘子已经只有一个了）。

　　4、到此任务下交完成，到各司其职完成的时候了。完成回推了：

第64个和尚移动第1个盘子，把它移开，然后第63个和尚移动他给自己分配的第2个盘子。
第64个和尚再把第1个盘子移动到第2个盘子上。到这里第64个和尚的任务完成，第63个和尚完成了第62个和尚交给他的任务的第一步。 

　　从上面可以看出，只有第64个和尚的任务完成了，第63个和尚的任务才能完成，只有第2个和尚----第64个和尚的任务完成后，第1个和尚的任务才能完成。这是一个典型的递归问题。 现在我们以有3个盘子来分析：

第1个和尚命令：

          ① 第2个和尚你先把第一柱子前2个盘子移动到第二柱子。（借助第三个柱子）

          ② 第1个和尚我自己把第一柱子最后的盘子移动到第三柱子。

          ③ 第2个和尚你把前2个盘子从第二柱子移动到第三柱子。 

　　　很显然，第二步很容易实现（哎，人总是自私地，把简单留给自己，困难的给别人）。

其中第一步，第2个和尚他有2个盘子，他就命令：

          ① 第3个和尚你把第一柱子第1个盘子移动到第三柱子。（借助第二柱子） 

          ② 第2个和尚我自己把第一柱子第2个盘子移动到第二柱子上。 

          ③ 第3个和尚你把第1个盘子从第三柱子移动到第二柱子。

　　　同样，第二步很容易实现，但第3个和尚他只需要移动1个盘子，所以他也不用在下派任务了。（注意：这就是停止递归的条件，也叫边界值）

第三步可以分解为，第2个和尚还是有2个盘子，命令： 

          ① 第3个和尚你把第二柱子上的第1个盘子移动到第一柱子。

          ② 第2个和尚我把第2个盘子从第二柱子移动到第三柱子。

          ③ 第3个和尚你把第一柱子上的盘子移动到第三柱子。 
                   
分析组合起来就是：1→3 1→2 3→2 借助第三个柱子移动到第二个柱子 |1→3 自私人留给自己的活| 2→1 2→3 1→3借助第一个柱子移动到第三个柱子|共需要七步。

如果是4个盘子，则第一个和尚的命令中第1步和第3步各有3个盘子，所以各需要7步，共14步，再加上第1个和尚的1步，所以4个盘子总共需要移动7+1+7=15步，同样，5个盘子需要15+1+15=31步，6个盘子需要31+1+31=64步……由此可以知道，移动n个盘子需要（2的n次方）-1步。

　　　从上面整体综合分析可知把n个盘子从1座（相当第一柱子）移到3座（相当第三柱子）：

（1）把1座上（n-1）个盘子借助3座移到2座。 
     （2）把1座上第n个盘子移动3座。 
（3）把2座上（n-1）个盘子借助1座移动3座。 

下面用hanoi（n,a,b,c）表示把1座n个盘子借助2座移动到3座。 

很明显:    (1)步上是 hanoi(n-1,1,3,2) 
               (3)步上是 hanoi(n-1,2,1,3) 
用C语言表示出来，就是：
#include <stdio.h>
int method(int n,char a, char b)
{     printf("number..%d..form..%c..to..%c.."n",n,a,b);     return 0;
}
int hanoi(int n,char a,char b,char c)
{     if( n==1 ) move (1,a,c);     else          {               hanoi(n-1,a,c,b);               move(n,a,c);               hanoi(n-1,b,a,c);          };     return 0;
}
int main()
{     int num;     scanf("%d",&num);     hanoi(num,'A','B','C');     return 0;
}

转载-递归算法详解（一）

转载原帖详见：http://chenqx.github.io/2014/09/29/Algorithm-Recursive-Programming/

Introduction

　　递归算法是一种直接或者间接调用自身函数或者方法的算法。递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。递归算法对解决一大类问题很有效，它可以使算法简洁和易于理解。递归算法，其实说白了，就是程序的自身调用。它表现在一段程序中往往会遇到调用自身的那样一种coding策略，这样我们就可以利用大道至简的思想，把一个大的复杂的问题层层转换为一个小的和原问题相似的问题来求解的这样一种策略。递归往往能给我们带来非常简洁非常直观的代码形势，从而使我们的编码大大简化，然而递归的思维确实很我们的常规思维相逆的，我们通常都是从上而下的思维问题， 而递归趋势从下往上的进行思维。这样我们就能看到我们会用很少的语句解决了非常大的问题，所以递归策略的最主要体现就是小的代码量解决了非常复杂的问题。
　　递归算法解决问题的特点：

• 递归就是方法里调用自身。
• 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。
• 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
• 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等，所以一般不提倡用递归算法设计程序。

　　递归算法要求。递归算法所体现的“重复”一般有三个要求：

　　(1) 是每次调用在规模上都有所缩小（通常是减半）；
　　(2) 是相邻两次重复之间有紧密的联系，前一次要为后一次做准备（通常前一次的输出就作为后一次的输入）；
　　(3) 是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。

从递归的经典示例开始

计算阶乘

　　计算阶乘是递归程序设计的一个经典示例。计算某个数的阶乘就是用那个数去乘包括 1 在内的所有比它小的数。例如，factorial(5) 等价于 5*4*3*2*1，而 factorial(3) 等价于 3*2*1。
　　阶乘的一个有趣特性是，某个数的阶乘等于起始数（starting number）乘以比它小一的数的阶乘。例如，factorial(5)与 5 * factorial(4) 相同。您很可能会像这样编写阶乘函数：

1 2 3

int factorial(int n){ return n * factorial(n - 1); }

(注：本文的程序示例用C语言编写)
　　不过，这个函数的问题是，它会永远运行下去，因为它没有终止的地方。函数会连续不断地调用 factorial。 当计算到零时，没有条件来停止它，所以它会继续调用零和负数的阶乘。因此，我们的函数需要一个条件，告诉它何时停止。
　　由于小于 1 的数的阶乘没有任何意义，所以我们在计算到数字 1 的时候停止，并返回 1 的阶乘（即 1）。因此，真正的递归函数类似于：

1 2 3 4 5 6

int factorial(int n){ if(n == 1) return 1; else return n * factorial(n - 1); }

　　可见，只要初始值大于零，这个函数就能够终止。停止的位置称为 基线条件（base case）。基线条件是递归程序的 最底层位置，在此位置时没有必要再进行操作，可以直接返回一个结果。所有递归程序都必须至少拥有一个基线条件，而且 必须确保它们最终会达到某个基线条件；否则，程序将永远运行下去，直到程序缺少内存或者栈空间。

斐波纳契数列

　　斐波纳契数列(Fibonacci Sequence)，最开始用于描述兔子生长的数目时用上了这数列。从数学上，费波那契数列是以递归的方法来定义：

　　这样斐波纳契数列的递归程序就可以非常清晰的写出来了：

1 2 3 4 5 6

int Fibonacci(int n){ if (n <= 1) return n; else return Fibonacci(n-1) + Fibonacci(n-2); }

递归程序的基本步骤

　　每一个递归程序都遵循相同的基本步骤：

(1) 初始化算法。递归程序通常需要一个开始时使用的种子值（seed value）。要完成此任务，可以向函数传递参数，或者提供一个入口函数， 这个函数是非递归的，但可以为递归计算设置种子值。
(2) 检查要处理的当前值是否已经与基线条件相匹配。如果匹配，则进行处理并返回值。
(3) 使用更小的或更简单的子问题（或多个子问题）来重新定义答案。
(4) 对子问题运行算法。
(5) 将结果合并入答案的表达式。
(6) 返回结果。

使用归纳定义

　　有时候，编写递归程序时难以获得更简单的子问题。 不过，使用 归纳定义的（inductively-defined）数据集 可以令子问题的获得更为简单。归纳定义的数据集是根据自身定义的数据结构 —— 这叫做 归纳定义（inductive definition）。
　　例如，链表就是根据其本身定义出来的。链表所包含的节点结构体由两部分构成：它所持有的数据，以及指向另一个节点结构体（或者是 NULL，结束链表）的指针。 由于节点结构体内部包含有一个指向节点结构体的指针，所以称之为是归纳定义的。
　　使用归纳数据编写递归过程非常简单。注意，与我们的递归程序非常类似，链表的定义也包括一个基线条件 —— 在这里是 NULL 指针。 由于 NULL 指针会结束一个链表，所以我们也可以使用 NULL 指针条件作为基于链表的很多递归程序的基线条件。
　　下面看两个例子。

链表求和示例

　　让我们来看一些基于链表的递归函数示例。假定我们有一个数字列表，并且要将它们加起来。履行递归过程序列的每一个步骤，以确定它如何应用于我们的求和函数：

(1) 初始化算法。这个算法的种子值是要处理的第一个节点，将它作为参数传递给函数。(2) 检查基线条件。程序需要检查确认当前节点是否为 NULL 列表。如果是，则返回零，    因为一个空列表的所有成员的和为零。(3) 使用更简单的子问题重新定义答案。我们可以将答案定义为当前节点的内容加上列表中     其余部分的和。为了确定列表其余部分的和， 我们针对下一个节点来调用这个函数。(4) 合并结果。递归调用之后，我们将当前节点的值加到递归调用的结果上。

　　这样我们就可以很简单的写出链表求和的递归程序，实例如下：

1 2 3 4 5

int sum_list(struct list_node *l){ if(l == NULL) return 0; return l.data + sum_list(l.next); }

汉诺塔问题

　　汉诺塔（Hanoi Tower）问题也是一个经典的递归问题，该问题描述如下：

汉诺塔问题：古代有一个梵塔，塔内有三个座A、B、C，A座上有64个盘子，盘子大小不等，大的在下，小的在上（如图）。有一个和尚想把这64个盘子从A座移到B座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。

　　Hanoi Tower Solving

• 如果只有 1 个盘子，则不需要利用B塔，直接将盘子从A移动到C。
• 如果有 2 个盘子，可以先将盘子1上的盘子2移动到B；将盘子1移动到C；将盘子2移动到C。这说明了：可以借助B将2个盘子从A移动到C，当然，也可以借助C将2个盘子从A移动到B。
• 如果有3个盘子，那么根据2个盘子的结论，可以借助c将盘子1上的两个盘子从A移动到B；将盘子1从A移动到C，A变成空座；借助A座，将B上的两个盘子移动到C。
  　　以此类推，上述的思路可以一直扩展到 n 个盘子的情况，将将较小的 n-1个盘子看做一个整体，也就是我们要求的子问题，以借助B塔为例，可以借助空塔B将盘子A上面的 n-1 个盘子从A移动到B；将A最大的盘子移动到C，A变成空塔；借助空塔A，将B塔上的 n-2 个盘子移动到A，将C最大的盘子移动到C，B变成空塔…
  　　根据以上的分析，不难写出程序：

1 2 3 4 5 6 7 8 9 10

void Hanoi (int n, char A, char B, char C){ if (n==1){ //end condition move(A,B);//‘move’ can be defined to be a print function } else{ Hanoi(n-1,A,C,B);//move sub [n-1] pans from A to B move(A,C);//move the bottom(max) pan to C Hanoi(n-1,B,A,C);//move sub [n-1] pans from B to C } }

将循环转化为递归

　　在下表中了解循环的特性，看它们可以如何与递归函数的特性相对比。

Properties	Loops	Recursive functions
重复	为了获得结果，反复执行同一代码块；以完成代码块或者执行 continue 命令信号而实现重复执行。	为了获得结果，反复执行同一代码块；以反复调用自己为信号而实现重复执行。
终止条件	为了确保能够终止，循环必须要有一个或多个能够使其终止的条件，而且必须保证它能在某种情况下满足这些条件的其中之一。	为了确保能够终止，递归函数需要有一个基线条件，令函数停止递归。
状态	循环进行时更新当前状态。	当前状态作为参数传递。

　　可见，递归函数与循环有很多类似之处。实际上，可以认为循环和递归函数是能够相互转换的。 区别在于，使用递归函数极少被迫修改任何一个变量 —— 只需要将新值作为参数传递给下一次函数调用。 这就使得您可以获得避免使用可更新变量的所有益处，同时能够进行重复的、有状态的行为。
　　下面还是以阶乘为例子，循环写法为：

1 2 3 4 5 6 7 8

int factorial(int n){ int product = 0; while(n>0){ product *= n; n--; } return product; }

　　递归写法在第二节中已经介绍过了，这里就不重复了，可以比较一下。

尾递归介绍

　　对于递归函数的使用，人们所关心的一个问题是栈空间的增长。确实，随着被调用次数的增加，某些种类的递归函数会线性地增加栈空间的使用 —— 不过，有一类函数，即尾部递归函数，不管递归有多深，栈的大小都保持不变。尾递归属于线性递归，更准确的说是线性递归的子集。
　　函数所做的最后一件事情是一个函数调用（递归的或者非递归的），这被称为 尾部调用（tail-call）。使用尾部调用的递归称为 尾部递归。当编译器检测到一个函数调用是尾递归的时候，它就覆盖当前的活动记录而不是在栈中去创建一个新的。编译器可以做到这点，因为递归调用是当前活跃期内最后一条待执行的语句，于是当这个调用返回时栈帧中并没有其他事情可做，因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个，这样所使用的栈空间就大大缩减了，这使得实际的运行效率会变得更高。
　　让我们来看一些尾部调用和非尾部调用函数示例，以了解尾部调用的含义到底是什么：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

int test1(){ int a = 3; test1(); /* recursive, but not a tail call. We continue */ /* processing in the function after it returns. */ a = a + 4; return a; } int test2(){ int q = 4; q = q + 5; return q + test1(); /* test1() is not in tail position. * There is still more work to be * done after test1() returns (like * adding q to the result*/ } int test3(){ int b = 5; b = b + 2; return test1(); /* This is a tail-call. The return value * of test1() is used as the return value * for this function.*/ } int test4(){ test3(); /* not in tail position */ test3(); /* not in tail position */ return test3(); /* in tail position */ }

　　可见，要使调用成为真正的尾部调用，在尾部调用函数返回之前，对其结果 不能执行任何其他操作。
注意，由于在函数中不再做任何事情，那个函数的实际的栈结构也就不需要了。惟一的问题是，很多程序设计语言和编译器不知道 如何除去没有用的栈结构。如果我们能找到一个除去这些不需要的栈结构的方法，那么我们的尾部递归函数就可以在固定大小的栈中运行。
　　在尾部调用之后除去栈结构的方法称为 尾部调用优化 。
　　那么这种优化是什么？我们可以通过询问其他问题来回答那个问题：

(1) 函数在尾部被调用之后，还需要使用哪个本地变量？哪个也不需要。
(2) 会对返回的值进行什么处理？什么处理也没有。
(3) 传递到函数的哪个参数将会被使用？哪个都没有。

　　好像一旦控制权传递给了尾部调用的函数，栈中就再也没有有用的内容了。虽然还占据着空间，但函数的栈结构此时实际上已经没有用了，因此，尾部调用优化就是要在尾部进行函数调用时使用下一个栈结构 覆盖 当前的栈结构，同时保持原来的返回地址。
　　我们所做的本质上是对栈进行处理。再也不需要活动记录（activation record），所以我们将删掉它，并将尾部调用的函数重定向返回到调用我们的函数。 这意味着我们必须手工重新编写栈来仿造一个返回地址，以使得尾部调用的函数能直接返回到调用它的函数。 　　

Conclusion

　　递归是一门伟大的艺术，使得程序的正确性更容易确认，而不需要牺牲性能，但这需要程序员以一种新的眼光来研究程序设计。对新程序员 来说，命令式程序设计通常是一个更为自然和直观的起点，这就是为什么大部分程序设计说明都集中关注命令式语言和方法的原因。 不过，随着程序越来越复杂，递归程序设计能够让程序员以可维护且逻辑一致的方式更好地组织代码。