Apart from recursive algorithms, stack size can be determined by static analysis.
Which reminds me: what is a good tool for analyzing / viewing a C++ programs call tree?
As already mentioned, perf can capture call stacks, but those are statistical samples, so not necessarily complete.
callgrind (https://www.valgrind.org/docs/manual/cl-manual.html) by contrast can capture all call-stacks.
kCacheGrind/qCacheGrind (https://kcachegrind.github.io/html/Home.html) can be used to view the output from either perf or callgrind. Sources for kcachegrind, including converters from perf, oprofile, etc., can be found at https://github.com/KDE/kcachegrind
Yes, this is true for comparison/search/sort/bucketing algorithms. But in other applications (e.g. graph theory, networks, sparse matrices) a depth of n, for n elements, can be perfectly legitimate. Or it can even be an edge case, but one you don't want to handle by just segfaulting.
> Which reminds me: what is a good tool for analyzing / viewing a C++ programs call tree?
Linux perf can collect the necessary data. Then for frontends, I am not sure. KDAB's "hotspot" ( https://www.kdab.com/tag/perf/ ) can do flamegraphs, but this may be more performance-oriented than what you're looking for.
Edit: perf can collect the data statistically. It will miss many calls, the ones that are the least time-consuming.
But in many contexts you have to be robust against a bad tree.
> Apart from recursive algorithms, stack size can be determined by static analysis.
Not always, in the presence of dynamically sized arrays (or alloca and friends).