需要一些帮助(如果可能的话)如何计算递归函数自身执行的次数。 我不知道如何在 OCaml 中制作某种计数器。 谢谢!
让我们考虑一个非常简单的递归函数(不是 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 |
|
|
---|---|---|
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) |
您可以像这样在任何更高的范围内创建引用
let counter = ref 0 in
let rec f ... =
counter := !counter + 1;
... (* Function body *)
如果较高的作用域恰好是模块作用域(或文件顶级作用域),您应该省略
in
您可以返回一个元组 (x,y),其中 y 在每次递归调用时加一。例如,如果您执行施罗德序列,它会很有用;)