数据结构和算法 函数调用栈和递归

        现代高级语言编译的程序几乎总是使用堆栈帧来存储每个过程或函数调用的工作内存。当任何过程或函数被调用时，一些栈帧被压入程序栈。当过程或函数返回时，这帧数据会从堆栈中弹出。

        1、栈有两种操作：压缩和弹出。

        2、所有函数调用都进入调用栈。

        3、调用栈可能很长，这将占用大量内存。

        4、普通递归每次函数调用，计算机都将为其在栈中分配内存。优化方法

        （1）重新编写代码，转而使用循环。

        （2）使用尾递归，但是并非所有语言都支持尾递归。

        5、尾递归的定义：如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。

        6、尾递归的原理：当编译器检测到一个函数调用是尾递归的时候，它就覆盖当前的活动记录而不是在栈中去创建一个新的。编译器可以做到这点，因为递归调用是当前活跃期内最后一条待执行的语句，于是当这个调用返回时栈帧中并没有其他事情可做，因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个，这样所使用的栈空间就大大缩减了，这使得实际的运行效率会变得更高。

        参考代码

int calc(int n, int res)
{
    if (n < 0)
        return 0;
    else if(n == 0)
        return 1;
    else if(n == 1)
        return res;
    else
        return calc(n - 1, n *res);
}

         7、python递归深度有限制，Python标准的解释器没有针对尾递归做优化，任何递归函数都存在栈溢出的问题。