第 23 讲：方法（二）：递归
前文我们介绍了方法的基本用法，以及调用方式。今天我们来说一下，方法递归的逻辑，以及用法。
Part 1 引例
前文，我们说到了一种调用方式，是通过 Main 方法调用 A 方法、B 方法和 C 方法的模式展开的。那么，方法的调用是可以串联的，比如 Main 方法里调用 A、A 里调用 B、B 里调用 C。
比如这样一个简单的例子。A 传入了一个带 ref 关键字的 a 变量。这表示数据在 A 方法里一旦修改，Main 方法里的 a 也发生改动。此时 A 方法里只对 a 增大一个单位后，调用了 B 方法。B 方法此时也是带 ref 参数、传入的 a，因此 Main、A 和 B 三个 a 用的是同一个 a 变量。此时 B 里增大 2 个单位 a，然后调用 C 方法。C 也是传入 ref 参数，因此 A、B、C 还有 Main 用的是是同一个 a。最后，a 增大三个单位在 C 方法里，至此，整个调用过程结束。待调用过程结束后，自动回退到最开始的调用方，即 Main 里。a 在期间增大了一共 6 个单位，因此 a
那么，有没有可能是下面这样的调用呢：
是的，你没有看错，A 方法里再次调用 A 自己。这个过程称为递归调用（Recursively Call）；而这种递归调用的思路，称为递归
Part 2 基本递归
显然，在前面这种递归示例里，我们无法退出调用过程。因为调用是“循环”的，A 里调用自己，那么 A 再次被得到调用；再次调用过程之中，A 又是一次调用自己，然后又再次得到一次调用。如此循环往复，无法退出来。这种递归称为无穷递归或死递归（Infinity Recursion）。显然，这种递归必然会导致程序挂掉，因为无穷无尽的调用只会无穷无尽地消耗内存资源。直到程序执行到某个时刻的时候，内存消耗得差不多了，程序就直接崩溃了。
显然，递归是危险的。但是递归有时候可以解决很复杂，也很有趣的问题。如果我们靠自己的逻辑来执行，可能连个思路都想不出来，这个时候递归可能会很有帮助。
2-1 示例 1：计算从 1 到 100 的和
这一次，我们使用递归的思维来完成这个例子。
递归就等于是找一个递推的思路。比如说通项公式使用递推的模式来表达，那么自然而然就可以用递归来完成了。比如说，从 1 到 100 的话，我们可以倒过来思考：假设 专门用来表示从 1 到 n 的和，即好比这个公式：
那么，我们找寻的递推式子可以这么考虑：我们要求的是 1 到 100，因此也就是 。而
不是吗？这就是我们这里所谓的递推公式。我们马上可以将其写成代码：
f 里再次使用了它自己。我们完成了递归的一半了。下面继续思考下一步。因为递归无法自己退出，因此这样写代码是显然不够的。它好比死循环一样，一旦进来就没办法自己出去。于是，我们得设定一个“界限”。当界限一旦触碰到的时候，就自动退出递归过程。那么，界限是哪里呢？还记得递推公式吗？这里的递推公式我们是从 100 开始算的。显然，数字到 1 的时候，我们难不成还继续算 f(1) = f(0) + 1 吗？显然没有必要了。因此，我们可以考虑自己手动录入 f(1) 的结果，这样的话，由于算到 f(1)
if (n == 1) return 1; else ... 的框架。这么做确实可以避免递归。因为 n == 1 条件成立的时候，此时会直接把 1 作为 F(1) 执行的结果而反馈给调用方，这样就没有再次继续调用 F 方法了。这就避免了继续递归。
我们试着调用一下 F 方法。
顺带一提，如果两个用
if-else连接的部分都带有return语句作为语句的话，那么else实际上是可以省略的。
这么写没有任何问题。原因很简单：因为
returnelse关键字。另外，我们把前文里直接将字面量作为
return语句的返回的那个部分称为递归出口（Exit）。递归出口是专门用来阻止继续无限制递归下去的过程的。
2-2 示例 2：兔子数列
简要说明一下兔子数列。兔子数列也叫斐波那契数列。兔子数列的通项公式很复杂：
显然这个数列完全没有帮助。不过我们要是写递归模式的话，式子可以这么搞：
那么，我们尝试为其改成代码：
下面我们看一下这个程序递归模式是不是可以完成计算。首先，将 F(100) 改成 F(99) + F(98)。然后 F(99) 和 F(98) 分别改成 F(98) + F(97) 和 F(97) + F(96)。然后这些数据，又被继续拆分计算。直到这些数据改成 F(1) 和 F(0) 的时候，会自动提出 0 和 1 的结果作为表达式结果，以此避免继续递归。
由于这里用到两次递归部分，一个是 F(n - 1)，而另外一个是 F(n - 2)。可以从 n 的取值看出，我们必须设定两个用来退出递归的 return 语句才行。
Part 3 尾递归
尾递归（Tail Recursion）是递归里的特别情况。我们牺牲一个方法的参数来存储每一次递归过程里计算出来的结果。当递归终止（递归出口触发）的时候，直接就把这个数据提取出来直接作为方法的返回值返回出去的表达方式。
3-1 示例 1：数组求和
这不是循环就能搞定吗？我们故意写一个递归让你明白递归怎么写。
数组求和实际上就是把数组数据挨个排开，然后逐个加起来的过程。显然，如果我们用 f(i) 表示到下标为 i 的时候，前面所有数据的和，那么 f(\text{arr.Length}) 就是我们要求的结果了。但是，光有个下标传入还不够，数组本身还没传入呢，我们肯定得传入一个数组进去。所以代码是这样的：
temp 来表示临时计算的结果。这个 temp 在调用方传入的时候是没有意义的，你给它规定为 0，表示从 0 开始计算。
在方法体里，我们先来看结果表达式 GetSum(arr, currentIndex + 1, temp + arr[currentIndex])。这个表达式可能不是很好理解。三个参数对应了方法本身的这三个参数。第一个参数自然是 arr，因为数组是不论如何都需要用到的；第二个参数是表示，递归的时候算到哪个索引了。在调用方（Main 方法），我们传入 0 表示初始从第 1 个元素开始计算。在递归的时候，显然我们递归就得计算下一个数据，因此索引在这里传入 currentIndex + 1 以表达下一次递归的时候，传入的参数是 1，即从第 2 个元素开始计算；第三个参数是 temp，用来临时记住递归的结果。初始的时候传入 0，而每一次运算都需要将前面的结果数值累计起来，因此下一次递归的 temp 数值应该是 temp + arr[currentIndex]（即原本的 temp 数值，加上数组当前索引下的数值）。
按道理来说，单说 currentIndex 变量的话，在递归的时候，必然会因为第二个参数总是传入原始数值 + 1 的关系，这个参数每次的数值就会变得越来越大。当 currentIndex == arr.Length 的时候，我们就可以认为递归可以结束了。因此，我们直接将累计结果的那个参数 temp 直接返回就可以了。至此，这就是这个题用递归写出来的方法。
那么，看下调用方的写法：
这样就可以了。
如果我们使用递归来完成这个操作的话，那么我们必然得找到一个递推公式。和前面这个例子一样，由于它和数学式子有所不同，因此不是很好表达成递归公式的形式。因此得自己想办法。
我们要用递归获取整个数组里最大的那个数，我们肯定最后是拿前面的比较结果和最后一个数一起比较的。因此，假设数学函数 f(i) 表示数组从 0 到 i 索引期间的最大值，那么我们可以这么表示：
其中的数学式子 就等价于 C# 里的条件运算符表达式
a > b ? a : b，即取这两个数的较大者。那么，整个功能要写成方法的话，可以考虑和前面这个例子实现的思路依葫芦画瓢：
其中，Math.Max
3-3 尾递归方法的入口点重载
显然，第二个参数和第三个参数暴露给用户是没有必要的，因为我们大家都知道，随时随地这两个参数都是 0（比如前面两个例子，都是传入 0 和 0 分别作为第 2 个和第 3 个参数）。既然如此，我们就没有必要让用户了解和知道这俩参数到底拿来干嘛。于是我们可以考虑重载一个没有这两个参数的方法，然后让这个方法专门调用递归方法。
我们拿前面这个例子举例说明。
然后，我们在使用递归方法的时候，可以直接使用前者即可。
这样一来，方法重载就会通过调用下面的方法来达到自动递归的效果，而且也体现了包装的思想。
Part 4 递归方法的条件运算符简写
很容易看出，前文给的例子全都可以用条件运算符来替换。因为 if (条件) return a; else return b; 的写法完全可以改成 return 条件 ? a : b;。因此，我们试着改写一下内容：
求从 1 到 n 的和：
兔子数列：
数组求和：
数组求最大值：
if-else 代换简写过来的写法，因此应当是等价的书写格式。只是使用条件运算符的话，不容易明白而已。
条件运算符里使用条件运算符的话，C# 是知道计算顺序的，因此不用使用小括号，因此前面兔子数列的结果可以直接去掉小括号这么写：
return n == 0 ? 0 : n == 1 ? 1 : F(n - 1) + F(n - 2);。
