计算递归调用的次数

Question

提醒一下，我是 ocaml/functional 编程的新手。
我有一个函数，它是计算施罗德数的递推关系之一。它在等式中调用自己两次。
我想计算给定输入时调用此函数的次数（我知道例如，对于 n = 6，函数调用自身 25 次），最好不使用可变性。
这是我现在的代码。它计算为 76 个函数调用。

let rec sn2 n k =  
  if n = 0 then 1, k 
  else if n = 1 then 2, k 
  else 
    let (a, b), (c, d) = sn2 (n - 1) (k + 1), sn2 (n-2) (k + 1) in 
    ((((6 * n - 3) * a) - ((n - 2) * c)) / (n + 1), b + d + k)

Answer 1

你的函数不需要一个参数来告诉它的调用者被调用了多少次。调用者可以负责这个号码（特别是因为你的代码无论如何都不是尾递归的）。

相反，该函数可以 return 1（因为它显然被调用）加上它进行的任何递归调用的计数 return。

let rec sn2 n =  
    if n = 0 then 1, 1
    else if n = 1 then 2, 1
    else
        let (a, b) = sn2 (n - 1) in
        let (c, d) = sn2 (n - 2) in
        ((((6 * n - 3) * a) - ((n - 2) * c)) / (n + 1), b + d + 1)

如果您只想计算“递归”调用（而不是最外层调用），您可以从最终计数中减去 1。

这是我尝试 n = 6 时看到的结果：

# sn2 6;;
- : int * int = (1806, 25)

这看起来与您要查找的计数非常接近。

（我希望这不是家庭作业。）

计算递归调用的次数

Count number of recursive calls

recursion

ocaml