Re: recursive algorithms and stack overflow

[Bruno Haible]

[CCing bug-gnulib and Marc Nieper-Wißkirchen.]

Paul Eggert wrote in <https://bugs.gnu.org/42931>:
> Bug#42931 prompted me to change the way 
> that the Gnulib diffseq module recurses so that the stack size is O(log N) 
> rather than O(N). I installed this change into Gnulib, here:
> 
> https://git.savannah.gnu.org/cgit/gnulib.git/commit/?id=7aadb23803a8fb71d07e6e87ffb1ca510d86f8ef

Similarly, there was a bug report against libcroco [1] recently, because
libcroco's CSS matching is recursive and can thus trigger stack overflow.

It seems this is something to watch out, when we have recursive algorithms
(which is quite frequent). Data sizes of 100 MB (or even just 100 KB) are
considered "small" by today's computation means; if they can trigger stack
overflow, users are unhappy.

Possible mitigations are:
  - Use iteration instead of recursion when possible - like here in diffseq.h,
  - Use iteration with a simulated heap-allocated stack - it would be useful
    to have the stack module in Gnulib for this (Marc?),
  - Use a recursion depth counter in some context struct, and check it at
    every recursion.

Do we have a list of the Gnulib modules that use recursion? [2]?

Bruno

[1] https://gitlab.gnome.org/Archive/libcroco/-/issues/8
[2] 
https://stackoverflow.com/questions/45194527/how-to-get-a-warning-for-using-recursion