一个时间冗杂度低的算法其实不代表任何情况下的效率都高。那是“现实”和“理论”的区别之一。如今我筹算来谈一下另一个比力“现实”的工具：编译器关于法式效率的影响。
那么我们先来看如许一段代码，假设有一个保留着整数的单向链表，要求您写一个函数停止乞降，您会怎么写呢？若是我们用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, int, int
public override int Invoke(FSharpList ls, int acc)
while (true)
FSharpList list = ls;
if (!(list is FSharpList。
_Cons))
return acc;
FSharpList。_Cons cons = (FSharpList。_Cons)list;
FSharpList xs = cons。get_Tail();
int x = cons。
get_Head();
acc += x;
ls = xs;