栈在递归中的应用

递归函数调用的特点：最后被调用的函数最先执行结束(LIFO)

函数调用时，需要用一个栈存储：调用返回地址、实参、局部变量

适合用“递归”算法解决：可以把原始问题转换为属性相同，但规模较小的问题

递归调用时，函数调用栈可称为“递归工作栈”，每进入一层递归，就将递归调用所需信息压入栈顶，每退出一层递归，就从栈顶弹出相应信息【缺点：效率低，太多层递归可能会导致栈溢出，可能包含很多重复计算】