Stack overflow when composing functions in F#

Question

Basically, my problem is that I'm trying to compose a very large number of functions, so I'm creating a deep chain of composed functions. Here is my code:

let rec fn (f : (State -> State option) -> (State -> State option)) (n : int) acc =
    match n with 
    | 0 -> acc 
    | _ -> fn f (n - 1) (f << acc)

and I make a call to it:

let foo = fn id 10000000 id bottom

So, it does ten milion iteration and it should combining lots of functions. I know for sure that fn is tail recursive (at least, I hope so), but the execution goes stack overflow and I can't figure out why.

At this point, the problem should be the deep cobination. So I was hoping for suggestions, tips, everything.

Answer 1

@BrianBerns's answer explains what's going on here, but I'd like to add a possible remedy.

Rather than using an acc variable to accumulate the monstrous composition of functions, take the seed argument and actually apply the function at every step:

let rec fn (f : (State -> State option) -> (State -> State option)) (n : int) arg =
    match n with 
    | 0 -> arg
    | _ -> fn f (n - 1) (f arg)

The meaning of this function is the same as your original: it applies function f to arg n times.

It is still tail-recursive, but it doesn't build up a big chain of composed functions.