那么我们先来看这样一段代码，假设有一个保存着整数的单向链表，要求您写一个函数进行求和，您会怎么写呢？如果我们用F#，那么最容易实现的自然是递归方式：
let rec sum ls =
match ls with
| [] -> 0
| x :: xs -> x + (sum xs)
这段F#代码使用了模式匹配：如果是一个空链表，那么其结果自然等于零，否则就把它第一个元素加上剩余元素之和。这段代码显然非常简单，通过声明式的方法“表达”了函数的逻辑，没有任何一句多余的代码。不过您一定发现了，这个函数的实现中使用了递归，因此对于长度为n的链表来说，这个函数的时间复杂度为O(n)，空间复杂度也是O(n)——空间的开销在函数的调用栈上。一般来说，递归总是难逃调用栈的累积，因此它的空间复杂度总是难以做到O(1)的常数级别。调用栈的堆积，使得程序在执行访问的内存地址跨度不断增大，容易导致程序的局部性（Locality）不佳，性能较差——关于代码局部性的影响，我们下篇文章中再进行讨论。
当然，有些朋友可能会说，为什么要用递归呢？用普通的一个for或while循环，然后不断累加不也可以吗？当然可以，而且这么做的话空间复杂度便是O(1)了，时间复杂度虽然还是O(n)，但是经过上面的描述，我们可以知道它的实际执行效率会比递归的方式要好。不过，for/while都是命令式编程的方式，不适合函数式编程的“声明”风格，因此在实际应用中我们往往会写这样的sum函数：
let sum ls =
let rec sum' ls acc =
match ls with
| [] -> acc
| x :: xs -> sum' xs (acc + x)
sum' ls 0
这个sum函数中定义了一个辅助函数sum'，这个辅助函数会多一个参数作为“累加器”，其中依旧使用了模式匹配的语法，在遇到空数组时直接返回累加器的值，否则就把链表的第一个元素加至累加器中，再递归调用sum'辅助函数。没错，这里还是用了递归。这样看起来，它的执行效果应该和前一种实现没有多大差别？
那么实际结果又是如何呢？如果您有条件不妨可以自己尝试一下——我这里贴一下由.NET Reflector反编译为C#后的sum'函数代码：
[Serializable]
internal class sum'@9 : OptimizedClosures.FSharpFunc<FSharpList<int>, int, int>
{
public override int Invoke(FSharpList<int> ls, int acc)
{
while (true)
{
FSharpList<int> list = ls;
if (!(list is FSharpList<int>._Cons))
{
return acc;
}
FSharpList<int>._Cons cons = (FSharpList<int>._Cons)list;
FSharpList<int> xs = cons.get_Tail();
int x = cons.get_Head();
acc += x;
ls = xs;
}
}
}
考试大温馨提示：本内容来源于网络，仅代表作者个人观点，与本站立场无关，仅供您学习交流使用。其中可能有部分文章经过多次转载而造成文章内容缺失、错误或文章作者不详等问题，请您谅解。如有侵犯您的权利，请联系我们，本站会立即予以处理。
相关推荐：
oracle中的rownum总结
oracle维护常用语句
数据库系统实现：数据库实现概论
