CODEWITHSUNDEEP
functional-programmingocaml
snfornroqsdm
snfornroqsdm

Reputation: 59

how do I count the amount of times a (recursive) function executes itself in ocaml?

needing some help (if possible) in how to count the amount of times a recursive function executes itself. I don't know how to make some sort of counter in OCaml. Thanks!

Upvotes: 0

Views: 154

Answers (2)

Chris
Chris

Reputation: 36660

Let's consider a very simple recursive function (not Schroder as I don't want to do homework for you) to calculate Fibonacci numbers.

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

Now, if we want to know how many times it's been passed in, we can have it take a call number and return a tuple with that call number updated.

To get each updated call count and pass it along, we explicitly call fib in let bindings. Each time c shadows its previous binding, as we don't need that information.

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)
  | _ -> invalid_arg "Negative values not supported"

And we can shadow that to not have to explicitly pass 0 on the first call.

let fib n = fib n 0

Now:

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

The same pattern can be applied to the Schroder function you're trying to write.

As a sidenote, this makes algorithmic complexity easy to see.

Consider for example the fib function above vs. a memoization approach defined as below using maps.

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 Diff
1 (1, 1) (1, 1) 0
2 (2, 4) (2, 3) 1
3 (3, 7) (3, 5) 2
4 (5, 13) (5, 7) 6
10 (89, 265) (89, 19) 246
20 (10946, 32836) (10946, 39) 32,797
30 (1346269, 4038805) (1346269, 59) 4,038,746
40 (165580141, 496740421) (165580141, 79) 496,740,342

Upvotes: 3

Ambika E
Ambika E

Reputation: 103

You can create a reference in any higher scope like so

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

If the higher scope happens to be the module scope (or file top-level scope) you should omit the in

Upvotes: 2

Related Questions