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!
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)
| _ -> raise (Invalid_argument "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)
| _ -> raise (Invalid_argument "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 |
---|---|---|
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) |