一直以来对于递归只是了解使用，最近在看javascript相关方面的书籍，看到用记忆功能优化递归，第一反应就是C#完全也可以实现，随即便测试了一下递归的各种方式。
首先先来看一下javascript的记忆递归：
var fibonacci = function () { var memo = [0, 1]; var fib = function (n) { var result = memo[n]; if (typeof result !== ‘number‘) { result = fib(n - 1) + fib(n - 2); memo[n] = result; } return result; }; return fib; }();
我们在一个名为memo的数组里保存我们的储存结果，储存结果可以隐藏之闭包中，当函数被调用是，这个函数首先检查结果是否已存在，如果已经存在，就立即返回这个结果。
正文：C#的递归和非递归
先来一个大家非常熟悉的普通递归：
static int Fibonacci(int n) { return n < 2 ? n : Fibonacci(n - 1) + Fibonacci(n - 2); }
这个递归大家一目了然我就不做过多的解释了，我们来看一下测试结果
现在来看一个我在网上找到的一个非递归模式：
static int Fibonacci(int n) {if (n <= 0) { return n; } int a = 1; int b = 1; for (int i = 3; i <= n; i++) { b = (a + b); a = b - a; } return b; }
由于递归的时间复杂度和空间复杂度较大，而且函数调用本身也会增加性能的开销，所以每多递归一次，所损耗的时间成本近乎成倍增加，而非递归模式内部做了循环调用，减少了递归调用的次数，测试结果
再来一个我根据javascript的记忆功能做的一个C#递归：
//声明一个记录递归值的集合 static List<int> array = new List<int>() { 0, 1 }; static int Fibonacci(int n) { int result = 0; if (array.Count <= n) { result = Fibonacci(n - 1) + Fibonacci(n - 2); array.Add(result); } else { result = array[n]; } return result; }
直接来看测试结果：
我们将每次递归的结果存到集合中，下次递归前先查询集合中是否当前递归值的结果，如果有直接返回，减少了递归调用的次数，时间的损耗也大大减少了。
还有一种递归方式把递归的的损耗也优化的非常不错，我们来看一下尾递归：
static int Fibonacci(int n, int ret1, int ret2) { if (n == 0) return ret1; return Fibonacci(n - 1, ret2, ret1 + ret2); }
第一个参数是递归次数，第二和第三个参数的递归开始的基础值，例如当前函数的调用方式：Fibonacci(10,0,1).我们来看一下测试结果：
通过对比我们发现尾递归运行的时间更短，效率更高，在实际应用中我们可以根据自己的需求去选择不同的方式实现，但是在此建议如果可以用非递归实现尽量不要用递归，递归可能会造成堆栈溢出，但是也并非否定递归，最终的决定权还是在开发者手中。
本文以上代码部分来自网络，如有侵权，请联系本人。
本文略显简陋，只用是用于博主记忆，若有错误，请指出，会做即使修改，谢谢。
原文：http://www.cnblogs.com/zk-f/p/6377570.html