递归和尾递归

递归

递归的概念：一个函数直接或间接的调用自身。

一般来说，递归调用需要有边界条件，递归前进段和递归返回段。
当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

递归一般用于解决三类问题：

1. 数据的定义是按递归定义的，如n的阶乘，斐波那契函数；

2. 问题解法是按递归实现的，如回溯；

3. 数据的数据结构是按递归定义的，如二叉树的遍历，图的搜索。

   [code]

   int factorial(int n) {
       if(n == 1){     //递归边界
           return 1;   //递归返回段
       } else {
           return n * factorial(n-1);  //递归前进段
       } 
   }

   机器层面的实现

   一个程序的执行在内存中就是一个个方法入栈和出栈的过程。堆栈中的每一个栈帧代表了被调用中的一个函数。

   例如计算factorial(4)的过程如图：
   

   计算factorial(4)的时候，方法是4*factorial(3)，但是还不知道factorial(3)的值，于是需要新增一个栈帧来计算，
   而factorial(3)需要factorial(2)……以此类推，到factorial(1)才能得到它的值，然后每个栈帧逐个出栈，最后计算得出factorial(4)的值。

   前面提到每个递归调用都需要一个边界条件，不满足该条件就会一直递归下去。但是内存中堆栈的容量是有限的，每个栈帧都需要占用空间，
   而且栈帧的维护也需要系统开销，递归层次太深可能会造成栈溢出。

   使用递归的优缺点

• 优点：
  精简代码，提高可读性；

• 缺点:

  1. 在自身中调用自身，是嵌套调用（栈帧无法回收，开销巨大）
  2. 递归层数过多时容易造成内存溢出问题

  递归的优化——尾递归

  递归的巨大开销是因为过多的栈帧占用空间和维护的巨大开销，这种调用是可优化的。
  之前的递归中递归前进段返回值为n * factorial(n-1)的表达式，这样每个栈帧都需要记录下当前的n的值，还要记录下一个函数栈帧的返回值，
  然后才能运算出当前栈帧的结果。也就是说使用多个栈帧是不可避免的。

  如果在函数返回的时候，调用自身本身，并且return语句不包含表达式，这样，编译器或者解释器就可以把递归进行优化，使递归无论调用多少次，
  都只占用一个栈帧，不会出现栈溢出的情况。