Recursion && given stack memory challenge

Question

I studied recursion on c programming and I have one concern about stack memory handling on recursive calls while recursive function is getting executed. specifically how things are done on stack memory ..

assume given this recursive function as following :

void recursion(int num) {


    if (num == 1 || num < 1 )
     {
       return ;
      }
     recursion(num/10);
}

assume num given as input 100 to the function, as well as we have stack memory given from 0 - 100 bytes , meaning that there is given implicitly integer array where its size from index 0 to 100. lets say given stackmemory[100] where recursion function work upon it

Now my concern is how I can by recursive calls keep tracking that I didnt arrive the maximum of stack memory? didnt reach stackover flow .. meaning how can I be sure that on the next recursive call that there is enough stack memory for next recursive call and if there is no sufficient space left on stack memory then recursion shall stop.

How I can keep tracking that? I was thinking about pointers to save/store some pointers aside and ampersend "&" related somehow to tackle that issue.

any idea or any help to tackle this issue? by the way the original function (given above recursion function) can be edited and to add any other additional functions ..

Thanks.

void recursion(int num) {


    if (num == 1 || num < 1 )
     {
       return ;
      }
     recursion(num/10);
}

Answer 1

assume num given as input 100 to the function, as well as we have stack memory given from 0 - 100 bytes

That's not making any sense. In your division algorithm, the value 100 has nothing to do with the amount of stack used. What's stacked (as per "calling convention") is the return address and the state of various registers depending on target, and in addition parameters may get stacked as well. An int parameter would then take up 4 bytes per call.

Your function here will have n=100, then n=10 and finally n=1, so 3 function calls. Depending on target, you might end up stacking something like (roughly) 4 to 16 bytes per call.

There is no "implicit integer array of size 100".

Also please note that recursion in the best case scenario can get optimized out. For example if we introduce a side effect to your function (so that it won't get 100% optimized out, which it currently will) then at least the latest gcc/x86 manages to remove the recursive call and replace it with a loop. (So-called tail call optimization.) https://godbolt.org/z/eP1s6E9Th Note that the assembly doesn't contain any call recursion instructions. This whole thing might get inlined into the caller code.

In fact this particular example was so trivial so that when including a caller code, it didn't even inline the function but replaced the whole thing with 3 printf statements printing 100, 10 and 1 respectively: https://godbolt.org/z/cGjaEEnfT

For more complex code the compiler might not be able to optimize it and that's when stack overflows and needlessly slow execution happen.

Now my concern is how I can by recursive calls keep tracking that I didnt arrive the maximum of stack memory?

You can't do that trivially. It would involve inline assembler that access the stack pointer before the first call, then check it inside each recursive call. The potential for stack overflow is one of the main reasons why recursion in C is regarded as dangerous and bad practice.

It might be possible to achieve in C through some very hackish means, such as dissecting the contents of a jmp_buf variable, then using setjmp/longjmp as a fail safe. Not something I'd recommend.

any idea or any help to tackle this issue?

Yes - don't use recursion. In some 99% of all algorithms you can come up with, recursion is almost certainly the wrong solution. Not only because it is dangerous, but also because it is slow and often hard to read.