Imagine I have the following pseudo code written in ocaml.
foo(n:int, d:int) = foo(n-1,d-1) + foo(n-1,d)
//Assume proper terminating conditions are added here
i.e. it is computing a recursively defined function.
The above is not tail recursive. A naive implementation of it will also lead to lots of redundant work being done (Like say the foo(n-1,d) computation will cause foo(n-1,d-1) to be called again)
I know that I can manually write this as a dynamic programming problem. I am not interested in that here
My question is , if I write it like this, will OCaml do something neat like memoize the nodes so that they are not recomputed. or some other fancy thing I cannot dream about?
No, OCaml doesn't do anything fancy with this code. If you want memoization you need to code it in explicitly.
Aside from the treating of tail calls as branches, and the inlining of small functions, OCaml generates the code that you would more or less expect. This is arguably one of its strengths (though you could also call it a weakness).