主页 / coding / 问题 / 77559447
Accepted
J.B
Asked: 2023-11-28 03:28:09 +0800 CST

OCaml 高阶函数

  • 772

有人请解释一下 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)

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

recursion

1 个回答

  1. Best Answer

    最后一个参数提供了一个累加器，这是在 OCaml 中实现尾递归的一种非常惯用的方法。通过参数提供的函数f提供了一种更新累加器的方法。

    递归函数中的每个路径要么需要是递归的退出，要么是对传递给函数的状态的更新。如果没有其中至少一个，我们就会陷入无限递归：无限循环。

    让我们看一下 的调用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

    在任何时候，我们都不需要通过调用堆栈来找到解决方案，因此可以将所使用的堆栈空间优化为常量。

    • 1

相关问题