两次调用同一递归函数比赋值给变量性能更差？OCaml性能疑问

哈哈，这个问题我刚入门OCaml的时候也踩过坑！核心原因其实很简单——第一段代码里的递归调用被执行了两次，而第二段只执行了一次，这直接导致了性能天差地别。

先把两段代码摆出来对比：

显式调用版本（性能劣） #

let rec max l = match l with 
  | x::[] -> x 
  | x::xs -> if(x > max xs) then x else max xs;;

变量缓存版本（性能优） #

let rec max l = match l with 
  | x::[] -> x 
  | x::xs -> let m = max xs in if (x>m) then x else m;;

关键区别：重复计算的坑 #

OCaml是严格求值的语言，也就是说表达式会在使用前完全计算。我们来拆解第一段代码的分支逻辑：
当处理x::xs时，代码会先计算if的条件x > max xs——这里会先调用一次max xs得到结果，用来和x比较。

• 如果条件为真（x更大），直接返回x，这还好；
• 但如果条件为假，就会进入else分支，再次调用一次max xs，然后返回这个结果。

也就是说，每次进入这个分支，只要x不是当前子列表的最大值，你就会重复计算一遍max xs！比如处理一个长度为n的列表，第一段代码的递归调用次数会是指数级的（大概2ⁿ次），而第二段代码里，我们用let m = max xs把递归结果存在变量里，只计算一次，之后不管是if还是else分支都直接复用这个值，调用次数是线性的（n次）。

举个小例子，比如列表[1,2,3,4,5]：

• 第二段代码只会递归调用max [2,3,4,5]、max [3,4,5]、max [4,5]、max [5]，总共4次递归；
• 第一段代码呢？计算max [1,2,3,4,5]时，条件1>max[2,3,4,5]为假，就会再算一次max [2,3,4,5]；而计算max [2,3,4,5]时，又会重复两次max [3,4,5]，以此类推，调用次数会爆炸式增长。

所以本质上就是重复计算导致的性能差异，第二段用变量缓存了递归结果，避免了不必要的重复调用，性能自然就上去了。

内容的提问来源于stack exchange，提问作者user9193072