如何计算（递归）函数在 ocaml 中执行自身的次数？

Question

需要一些帮助（如果可能的话）如何计算递归函数自身执行的次数。 我不知道如何在 OCaml 中制作某种计数器。 谢谢！

Answer 1

让我们考虑一个非常简单的递归函数（不是 Schroder，因为我不想为你做作业）来计算斐波那契数。

let rec fib n =
  match n with
  | 0 | 1 -> 1
  | _ when n > 0 -> fib (n - 2) + fib (n  - 1)
  | _ -> raise (Invalid_argument "Negative values not supported")

现在，如果我们想知道它被传入了多少次，我们可以让它获取一个索书号并返回一个更新了该索书号的元组。

为了获取每个更新的调用计数并将其传递，我们在 let 绑定中显式调用

fib

。每次

c

都会隐藏其之前的绑定，因为我们不需要该信息。

let rec fib n c =
  match n with
  | 0 | 1 -> (1, c + 1)
  | _ when n > 0 -> 
    let n',  c = fib (n - 1) (c + 1) in
    let n'', c = fib (n - 2) (c + 1) in
    (n' + n'', c)
  | _ -> raise (Invalid_argument "Negative values not supported")

我们可以隐藏它，以便不必在第一次调用时显式传递

0

。

let fib n = fib n 0

现在：

# fib 5;;
- : int * int = (8, 22)

相同的模式可以应用于您尝试编写的施罗德函数。

---

顺便说一句，这使得算法的复杂性很容易看出。

例如，考虑上面的

fib

函数与使用映射定义如下的记忆方法。

let fib_fast n =
  let module M = Map.Make (Int) in
  let rec aux ?(cache=M.of_list [(0, 1); (1, 1)]) ?(c=1) n =
    if n < 0 then invalid_arg "Negative values not supported."
    else
      match M.find_opt n cache with
      | Some r -> (r, c, cache)
      | None ->
        let (r', c, cache) = aux ~cache ~c:(c+1) (n - 1) in
        let (r'', c, cache) = aux ~cache ~c:(c+1) (n - 2) in
        let r = r' + r'' in
        (r, c, M.add n r cache)
  in
  let (r, c, _) = aux n in
  (r, c)

n	fib	fib_fast
1	(1, 1)	(1, 1)
2	(2, 4)	(2, 3)
3	(3, 7)	(3, 5)
4	(5, 13)	(5, 7)
10	(89, 265)	(89, 19)
20	(10946, 32836)	(10946, 39)
30	(1346269, 4038805)	(1346269, 59)
40	(165580141, 496740421)	(165580141, 79)

Answer 2

您可以像这样在任何更高的范围内创建引用

let counter = ref 0 in
let rec f ... =
  counter := !counter + 1;
  ... (* Function body *)

如果较高的作用域恰好是模块作用域（或文件顶级作用域），您应该省略

in

Answer 3

您可以返回一个元组 (x,y)，其中 y 在每次递归调用时加一。例如，如果您执行施罗德序列，它会很有用;)