It certainly appears that all these data must be replicated on stack for each recursive call.  I don't see that a generalization could be made about the performance, even if I assume that your alternative is an array of those "complicated structures."  If there is no reason for each instance to have its own copy of those arrays, it seems you could get better cache locality by sharing a single copy, if only one thread is involved.