查找列表中的项并返回其索引- OCaml

Question

我编写了以下函数来查找给定列表"lst"中的给定项"x"并返回其索引，否则将返回错误:

exception Failure of string
let rec func x lst c = match lst with
    | [] -> raise(Failure "Not Found")
    | hd::tl -> if (hd=x) then c else func x tl (c+1)

let find x lst = func x lst 0

函数是完全工作的，我只是想知道它的内存消耗是多少?这意味着内存消耗是否取决于列表的长度?还是O(1)?

如果不是0(1)，谁能告诉我应该怎么做?

谢谢

Answer 1

你的函数消耗常量(O(1))空间，因为它是尾部递归的。

你可以在OCaml.org上阅读尾部递归，在这里。

这是一个非尾递归解:

exception Failure of string
let rec find x lst =
    match lst with
    | [] -> raise (Failure "Not Found")
    | h :: t -> if x = h then 0 else 1 + find x t

(我刚刚注意到PatJ已经解释过了，对不起:-)

通常非尾递归的解决方案更简洁优雅。这太糟糕了，但世界有时就是这样。