Count number of recursive calls-CodePudding

Just as a heads-up, I'm a total newbie in ocaml/functional programming.
I have a function, which is one of the recurrence relations for calculating Schröder numbers. It calls itself two times in the equation.
I want to count the number of times this function is called when an input is given (I know that for example, for n = 6 the function calls itself 25 times), preferably without using mutability.
This is the code I have right now. It evaluates to 76 function calls.

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)

CodePudding user response：

Your function doesn't need a parameter telling how many times its caller has been called. The caller can take charge of this number (especially since your code isn't tail recursive anyway).

Instead, the function can just return 1 (because it clearly was called) plus the counts returned by any recursive calls it makes.

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)

If you only want to count "recursive" calls (and not the outermost call) you can subtract 1 from the final count.

Here's what I see when I try n = 6:

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

This looks pretty close to the count you were looking for.

(I hope this wasn't a homework assignment.)