栈在递归中的应用

若在一个函数、过程或数据结构的定义中又应用了它自身，则这个函数、过程或数据结构称为递归定义的，简称递归。

递归目的

递归的目的通常是将一个大型的复杂问题层层转化为一个与原问题相似的且规模较小的问题来求解。

递归优点

代码简洁、便于理解

递归缺点

时间和空间消耗大、可能存在栈溢出、可能存在重复计算。

通常情况下，它的效率并不是很高。

递归和栈的关系

递即进栈，归即出栈

int Fib(int n ) {	//斐波那契数列的实现
	if (n == 0)
        return 0;	//边界条件
    else if (n == 1)
        return 1;	//边界条件
    else
        return Fib(n - 1) + Fib(n - 2);	//递归表达式
}

递归表达式即递归体，边界条件即递归出口。

问题：咦，栈在递归中的应用，可是这个代码中也没有栈啊？

回答：这是因为函数的每次调用，就是一个栈。递归调用时，函数调用栈可称为递归工作栈,每进入一层递归，就将递归调用所需信息压入栈顶，每退出一层递归，就从栈顶弹出相应信息。因此，递归的实现是离不开栈的。

---

使用栈可以模拟递归的过程，以此来消除递归，但对于单向递归和尾递归而言，可以用迭代的方式来消除递归。

单向递归：指程序中的递归语句，在本程序操作执行前，都已经完成，如斐波那契数列
尾递归：程序中只有一句递归语句，且在末尾。