算法之递归（1）

最近事情太多了，很少有时间可以完全静下来认真研究一些东西；每当专注的写代码的时候，总是被其他事情打断。还好，礼拜天来了，总算可以抽出一些时间了J

《代码之美》第一章有一个关于模式匹配的问题，即根据正则表达式在相应的文本中找到匹配的值，找到返回1，没找到返回0。撇开具体的实现，里面优美的递归调用倒是深深地吸引了我。于是，我开始重新思考递归，毕竟有些细节之前的思考还不够到位。

什么是递归

我的印象中的递归是函数调用自身来完成预先定义的操作。当然，实际涉及的内容更多，比如退出递归的条件，代码逻辑，参数等等。

可以将递归理解为栈，即调用序列是以顺序结构的形式并遵循后进先出的顺序存放在栈中的。举个例子来说，加入存在这样的调用A()->B()->C()->D()，那么其在栈中的顺序如下，

A() : int

B() : int

C() : int

D() : int

通过这个例子不难看出，将B，C，D的名字全部换成A，就是递归调用A的全部过程。

我们来看一个具体的例子，如何计算1到N个自然整数的和。

{1， 2， 3， 5， …， n}

解法一

定义一个全局变量，用来做存储当前的和。

具体实现如下

int sum = 0;

private void GetSum(int n)

{

if (n == 0) return;

if (n < 0)

throw new ArgumentException("Invalid input.");

sum += n;

GetSum(n - 1);

}

这个递归逻辑上没有问题，但是多定义了一个变量，作为最终的用户，需要在其上面再封装一层可以使用。当然，也可以在写一个函数重新封装，然后expose这个wrap后的版本。

那么有没有更好的解决方案？

解法二

定义一个有返回值的函数。

开篇的时候，我介绍递归类似于堆栈，所以递归调用也遵循后调用现出的原则。如果加上返回值，那么就只需要计算当前的n值于n之前所有值的和即，便可以得到n个数的和。比如有10个数，当前n是5，那么这层递归是5的和。

我们先来看一下代码，然后再做具体的分析。

private int GetSumWithReturn(int n)

{

if (n < 0)

{

throw new ArgumentException("Invalid input.");

}

if (n == 0)

return 0;

return n + GetSumWithReturn(n - 1);

}

分析解法二

当n小于0是，认为是一个非法操作。
当n等于0是，认为是已经计算到最小值，此时可以退出递归。
返回当前n的值与n-1之前

以n等于5为例，栈的结构如下，注意，从下自上看并且注意高亮的部分。（因为栈的顺序写反了，所要从下自上看，下面是栈顶)

Function Call	Function Body
GetSumWithReturn(5)	private int GetSumWithReturn(int n) // n = 5 { if (n < 0) { throw new ArgumentException("Invalid input."); } if (n == 0) return 0; return n + GetSumWithReturn(n - 1);// 5 + 10 = 15， return 15 }
GetSumWithReturn(4)	private int GetSumWithReturn(int n) // n = 4 { if (n < 0) { throw new ArgumentException("Invalid input."); } if (n == 0) return 0; return n + GetSumWithReturn(n - 1);// 4 + 6 = 10， return 10 }
GetSumWithReturn(3)	private int GetSumWithReturn(int n) // n = 3 { if (n < 0) { throw new ArgumentException("Invalid input."); } if (n == 0) return 0; return n + GetSumWithReturn(n - 1);// 3 + 3 = 6， return 6 }
GetSumWithReturn(2)	private int GetSumWithReturn(int n) // n = 2 { if (n < 0) { throw new ArgumentException("Invalid input."); } if (n == 0) return 0; return n + GetSumWithReturn(n - 1);// 2 + 1 = 3， return 3 }
GetSumWithReturn(1)	private int GetSumWithReturn(int n) // n = 1 { if (n < 0) { throw new ArgumentException("Invalid input."); } if (n == 0) return 0; return n + GetSumWithReturn(n - 1);// 1 + 0 = 1， return 1 }
GetSumWithReturn(0)	private int GetSumWithReturn(int n) // n = 0 { if (n < 0) { throw new ArgumentException("Invalid input."); } if (n == 0) // n = 0, then return 0. return 0; return n + GetSumWithReturn(n - 1); }