oCaml 高阶函数

Question

请有人为 oCaml 解释一下这个问题的算法。

我有解决方案，但我不明白。

定义 iterup：(int * 𝛼 → 𝛼) → int → int → 𝛼 → 𝛼。 Iterup 采用一个接收当前数字和累加器的函数。它从给定的开始到给定的结束递增计数器编号，并每次应用该函数。最后一个参数是累加器的起始值。

解决办法是

let rec iterup f st ed acc = 
  if st > ed then 
    acc 
  else 
    iterup f (st+1) ed (f st acc)

我不明白的是为什么我们在最后一部分（f n s）中同时采用 n 和 s 作为 f 的参数。当我们谈论尾递归时，这给我们带来了什么？

Answer 1

最后一个参数提供了一个 accumulator，这是在 OCaml 中实现尾递归的一种非常惯用的方法。

让我们看一下

iterup

的电话。

iterup (fun a b -> a + b) 1 5 0
iterup (fun a b -> a + b) 2 5 (0 + 1)
iterup (fun a b -> a + b) 3 5 (1 + 2)
iterup (fun a b -> a + b) 4 5 (3 + 3)
iterup (fun a b -> a + b) 5 5 (6 + 4)
iterup (fun a b -> a + b) 6 5 (10 + 5)
15

我们无需通过调用堆栈来查找解决方案，因此可以优化所使用的堆栈空间以使其保持不变。