[notact]

If writing a recursive algorithm on arbitrary input, check remaining stack size upon recursive function entry. If space is depleted, allocate a new fiber (aka a brand new clean stack), switch to it, and resume. Switch back to calling fiber on stack unwind.

[10000truths]

If you’re writing a recursive algorithm on arbitrary input, you should be using a stack container to store your state, not the call stack.

[notact]

Why do you think so? A stack container ordinarily contains a single data type. You can jump through some hoops to let it store completely arbitrary types, but when you consider a function's stack frame as a distinct type, the call stack naturally does that for you.

[10000truths]

1. A stack frame usually takes up far more memory than the state that actually needs to be persisted, due to local variables and padding from alignment requirements. With a stack container, you can specify exactly what gets stored, and save on your memory footprint.

2. There are very few knobs you can tweak to control how your call stack space is allocated or represented in memory. With a stack container, you have much finer control over that - you can do reallocations or define custom error handling when you overflow the container, you can deallocate/shrink the container when you no longer need the space, you can serialize the container to disk to make your processing resumable, etc.

3. A call stack has a very limited set of operations. You can only access data from the current stack frame, and you can only push/pop (call/return) stack frames. But with your own stack-like data structure, you could extend it to do far more, e.g. accessing data from the first or last n traversals, or insert/remove multiple elements at once.

[kragen]

Most commonly you handle this with a stack of records.

[sydthrowaway]

you mean std::stack?