Stack Size Estimation

Runtime-Evaluation

An online method is to paint the complete stack with a certain value, like 0xAAAA (or 0xAA, whatever your width is). Then you can check how large the stack has maximally grown in the past by checking how much of the painting is left untouched.

Have a look at this link for an explanation with illustration.

The advantage is that it's simple. A disadvantage is that you cannot be certain that your stack size won't eventually exceed the amount of used stack during your testing.

Static Evaluation

There are some static checks and I think there even exists a hacked gcc version that tries to do this. The only thing I can tell you is that static checking is very difficult to do in the general case.

Also have a look at this question.

How to determine maximum stack usage?

The most common way to determine the deepest stack usage is to initialize the stack memory with some known but unusual value, then periodically (or at the end of a big test run) see where that pattern stops.

This is exactly how the IAR IDE determines the amount of stack used.

How to measure a functions stack usage in C?

Using warnings

This is GCC specific (tested with gcc 4.9):

Add this above the function:

#pragma GCC diagnostic error "-Wframe-larger-than="

Which reports errors such as:

error: the frame size of 272 bytes is larger than 1 bytes [-Werror=frame-larger-than=]

While a slightly odd way method, you can at least do this quickly while editing the file.

Using CFLAGS

You can add -fstack-usage to your CFLAGS, which then writes out text files along side the object files.
See: https://gcc.gnu.org/onlinedocs/gnat_ugn/Static-Stack-Usage-Analysis.html
While this works very well, its may be a little inconvenient depending on your buildsystem/configuration - to build a single file with a different CFLAG, though this can of course be automated.
– (thanks to @nos's comment)

Note,

It seems most/all of the compiler natural methods rely on guessing - which isn't 100% sure to remain accurate after optimizations, so this at least gives a definitive answer using a free compiler.

C/C++ maximum stack size of program on mainstream OSes

In Visual Studio the default stack size is 1 MB i think, so with a recursion depth of 10,000 each stack frame can be at most ~100 bytes which should be sufficient for a DFS algorithm.

Most compilers including Visual Studio let you specify the stack size. On some (all?) linux flavours the stack size isn't part of the executable but an environment variable in the OS. You can then check the stack size with ulimit -s and set it to a new value with for example ulimit -s 16384.

Here's a link with default stack sizes for gcc.

DFS without recursion:

std::stack<Node> dfs;
dfs.push(start);
do {
    Node top = dfs.top();
    if (top is what we are looking for) {
       break;
    }
    dfs.pop();
    for (outgoing nodes from top) {
        dfs.push(outgoing node);
    }
} while (!dfs.empty())

Calculation of stack size in FreeRtos or TI rtos

The compiler, compiler optimisation level, CPU architecture, local variable allocations and function call nesting depth all have a large impact on the stack size. The RTOS has minimal impact. For example, FreeRTOS will add approximately 60 bytes to the stack on a Cortex-M - which is used to store the task's context when the task is not running. Whichever method you use to calculate stack usage in your non-RTOS project can be used in your RTOS project too - then add approximately 60 bytes.

You can calculate these things, and that can be important in safety critical applications, but in other cases a more pragmatic approach is to try it and see - use the features of the RTOS to measure how much stack is actually being used and use the stack overflow detection - then adjust until you find something optimal.
http://www.freertos.org/Stacks-and-stack-overflow-checking.html
http://www.freertos.org/uxTaskGetStackHighWaterMark.html

Stack Size Estimation