调用栈

调用栈

递归算法所需的空间取决于递归深度而不是递归实例数

消除递归

为维护调用栈，需花费额外的时间和空间，为节省空间，可以显式地维护调用栈，将递归改为迭代。 通常是在常数意义下优化空间，但也有可能带来实质改进。

尾递归

唯一的递归位于函数的末尾。 一旦抵达递归基，会触发一系列返回，并未用到老帧的信息。 可通过直接覆写老帧消除递归。

头递归

唯一递归位于函数头部。 通过显式维护一个栈代替递归调用栈，空间复杂度不变，常系数更小。