C#开发笔记之06-为什么要尽可能的使用尾递归，编译器会为它做优化吗？

C#开发笔记概述

概述

从A函数跳转到B函数，在B函数执行完毕后，程序为什么能精确的返回到A函数中未执行完的代码区域？

解释

首先，我们要知道什么是栈和栈帧。

栈是一种特殊的线性表，仅能在线性表的一端-栈顶进行操作，栈底不允许操作。
栈的特性：后进先出（Last In First Out or LIFO）

栈帧是一个函数执行的环境：函数参数、函数的局部变量、函数执行完后返回到哪里等。

为了我们不会因为文字的描述而产生歧义，我们约定程序从左向右运行，左边为前，右边为后。

从函数A跳转到函数B时，将函数的执行环境压入栈中，显然栈帧就是栈中所需要存放的数据。函数B执行完成后，运行环境知道，刚执行完成了一个函数，现在要回到某个地方了，那么回到哪里呢？当然是从栈中弹出最近一个栈帧（如果有的话）并取出相关信息即可。

这堪称是一个完美的设计！这种设计为函数式编程带来了高可靠性的同时也带来了性能损失。事实上运行环境维护这样的数据结构并不轻松，首先我们需要一个特殊的数据区域来存放这个栈，这个栈通常被称为“调用堆栈”（Call Stack），并且通常有 1M 的空间限制（注意这个值是可以改的）和 2^32 次的数量限制（32位系统，一般情况下 1M 的空间限制首先到达）。即每次从一个函数跳转到另外一个函数会使栈增加一个计数并存放栈帧信息，下次程序执行路径在函数终点处需要返回时又要从栈中取出栈顶信息（如果有的话）。但情况并非总是如此！

一般情况下总是需要这样的一个栈帧，但如果函数A跳转到函数B时，该处已经是函数A的最后一句是又会怎么样呢？显然，这个栈帧不是必须的，因为返回此处时，由于函数A也即将结束，又会往前返回到上一个栈帧，那何不直接返回到上一个栈帧呢？事实上现代编译器都会为这种情况做出优化，运行时不会为其增加栈帧，而是在函数B运行完成后，直接返回至函数A之前所存放的栈帧信息（如果有的话）。显然递归属于特殊函数的跳转，它跳转到其本身。

再来看看什么是尾递归。

如果一个函数中所有递归形式的调用都出现在函数的末尾（逻辑上的末尾或者说代码路径的末尾），我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。

我们通过1个案例来具体的分析一下，之后再回头看上面的描述可能会更加清楚的了解运行环境是如何追踪函数的运行状态的。

public class Program {

    public static void Main(string[] args) {
        Add(100);
        Add(95);
        Add(80);
        Console.ReadKey();
    }

    private static void Add(int score) {
#line 100
        if(score == 100) {
            Perfect();
        }
        //请注意这里是另起if
#line 200
        if(score >= 90) {
            Excellent();
        } 
#line 300
        else {
            ComeOn();
        }
    }

    private static void Perfect() {
        Console.WriteLine("Perfect!");
    }

    private static void Excellent() {
        Console.WriteLine("Excellent!");
    }

    private static void ComeOn() {
        Console.WriteLine("ComeOn!");
    }

}

我们先来分析 Add(100) 的执行，Main->Add->Perfect，每次跳转函数都会增加一个栈帧，以便程序执行可以沿着 Perfect->Add->Main 这样的路径往前返回。在这个过程中显然每次函数的跳转都会增加栈帧。

如果你已经明白了 Add(100) 的执行过程，那么现在要分析的 Add(90) 的执行过程可能不会太难。但需要注意到的一点是，当分数为90的时候，第100行的代码（#line 100）被执行到的时候，运行环境已经知道这是最后一行可以被执行到的代码，因为 if else 中只有一个可以被命中的路径，所以程序往前返回时的路径是这样的 Excellent->Add->Main （删除线部分表示未被返回） 。因为 Add(90) 跳转到 Excellent 方法时，没有为其增加栈帧，因为完全没有必要。显然 Add(80) 也是这样的。

接一下，我们再看看函数有返回值时，会出现什么情况。

private static void Add(int score) {
    string description = string.Empty;
#line 100
    if(score == 100) {
        description = Perfect();
    }
    //请注意这里是另起if
#line 200
    if(score >= 90) {
        description = Excellent();
    }
#line 300
    else {
        description = ComeOn();
    }
}

private static string Perfect() {
    return "Perfect!";
}

private static string Excellent() {
    return "Excellent!";
}

private static string ComeOn() {
    return "ComeOn!";
}

在分析这种情况前，我们再来回顾一下尾递归的概念：

如果一个函数中所有递归形式的调用都出现在函数的末尾（逻辑上的末尾或者说代码路径的末尾），我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。

显然，当需要这个函数的返回值时，其不属于尾递归。