Maximum Depth of a Call Hierarchy

Question

I've been wondering for some time now what's the maximum depth for a call hierarchy. If I have a big method, after refactoring, I often come to code looking like this:

void A()
{
    //...
    B();
}

void B()
{
    //...
    C();
}

void C()
{
    //...
}

So I am calling a method which calls a method which calls a method (and so on) - all in the same class. Is there a rule of thumb how many levels are too many? (And is the term "call hierarchy" correct for this issue?)

Would it be better if I refactor so that A somehow calls both B and C?

Answer 1

I often see junior developers complain about heavily factored out code that the call stack is too deep to keep track of. They especially complain about it during debugging. Sometimes when first learning the code as well. I usually answer with a question:

If "printf" was implemented internally using 12 functions does it matter? (and I've seen implementations where this is sort of true, it was 4 functions not 12 but the point holds)

The truth is, if at any point in the code you need to dig through more than two levels to understand what's going on then you haven't named your functions properly or your function prototype/API is confusing. Whichever it is it's a sign of bad design.

Personally I don't see actual call depth per se as a problem. It's just that if it ever manifest itself as a problem then it's a symptom of badly named or designed code.

• If you need to pass an argument unchanged through more than one layer of functions than that argument should be a private variable of the class.
• Sometimes a deep call stack within a single class indicates that the chain of functions are actually simple functions that's been prematurely coupled. It's often better to write simple functions that accept an argument and return something and then explicitly call them like: C(B(A())). In other words, keep your code orthogonal.
• If when reading the code you're forced to dig through layers of functions then the functions have not been named properly.
• If the functions are well named but you still need to dig through layers then it could indicate that you have another class hidden in your class. Refactor the code to extract the functionality of the deepest functions into its own class because it seems to be doing other things not directly related to what the class is supposed to do.

Answer 2

Short answer: That all depends on your programming language, and on how the machine that your program is running on is configured.

Long Answer:

There is no theoretical limit, although there may be mechanical limits. This is in the same sense that there is no largest number as such, but there will always be a limit to how large a number you can actually write down or store in a computer's memory.

Many programming language implementations employ a call stack, and the machines that run them often have explicit support for such a stack in their instruction set that your program ultimately is translated to. The stack is a region of memory that is statically allocated and usually has a fixed size. Whenever your program makes a method call, the machine will push a reference to that place in your program onto the stack. When the method call has finished, the machine can continue executing your method where it left off and remove that "frame" from the stack. If your program makes a lot of nested calls, it may need to push more frames onto the stack than there is room for. This will cause your program to crash with a Stack Overflow Error. Assuming this is the whole story, the practical limit of the depth of your "call hierarchy" is the size of the program's call stack.

But that is not the whole story. If calling another method is the last thing that a method does (i.e. it is in tail position), then there is no reason to push that call onto the stack because the program will not need to return to that place again. This kind of call is a tail call. A correct programming language implementation will be written so that it respects tail calls by not pushing them onto the stack. This is known as tail call elimination. Under such circumstances, your program can make as many nested calls as you want, provided that they are in tail position. You can even write programs that are infinitely recursive.

Some programming language implementations are stackless, so their execution models do not employ a stack at all. Then they will have some central execution machinery that registers method calls, such as a trampoline or an execution queue that may be serviced by a thread pool. Even in a language that traditionally uses the stack, you can employ these techniques yourself to make your programs stackless.

Find out whether your language uses a stack, how you would go about configuring its size, and whether or not it is capable of tail call elimination.