# Thread: Recursion && given stack memory challenge.

1. ## Recursion && given stack memory challenge.

Hi ,
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 :

Code:
```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
Code:
` 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? for not reaching stack over 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.

2. Originally Posted by AkamiKhmenisky
Hi ,
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 :

Code:
```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
Code:
` 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? for not reaching stack over 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.
If you are so concerned about blowing the stack using recursion, then change the algorithm to avoid recursion. Don't try to track the stack!

Adding function calls within the recursive function just complicates the recursion possibly exponentially, depending on the functions called, especially if you can't see the source of the functions, to see what functions they call or how much memory on the stack is used!

To prematurely end recursion and not fully complete the recursive code, you will probably get an inaccurate answer, or value, unless you return some error indicator.

Also:
Code:
```void recursion(int num) {

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

3. Originally Posted by rstanley
If you are so concerned about blowing the stack using recursion, then change the algorithm to avoid recursion. Don't try to track the stack!

Adding function calls within the recursive function just complicates the recursion possibly exponentially, depending on the functions called, especially if you can't see the source of the functions, to see what functions they call or how much memory on the stack is used!

To prematurely end recursion and not fully complete the recursive code, you will probably get an inaccurate answer, or value, unless you return some error indicator.

Also:
Code:
```void recursion(int num) {

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

Thanks much for your response and feedback, all what you're saying make sense and I consent with. but again this is the challenge or the problem is to tackle what I asked for which is to keep track / trace the stackmemory which is given implicitly as int stackmemory[100].

So what Im thinking about maybe to convert this recursion function to assembly language and then to write some coditions on stackover flow?

again my concern is this :
assume lets say on first call on the function recursion() its f1 , now it occupies lets say 16 bytes ( assume yes occupies 16 bytes) , so next recursive call f2 will occupy also 16 bytes , third recursive call also f3 will occupy 16 bytes .. till lets say f6 call so on total we occupied from stackmemory under our case is 16*6 = 96 and it's smaller than 100 so that's fine , now next f7 call it will lead to stackover flow since we only have 100Bytes lets say and we already occupied 96 byte so 128bytes ( 16*7) is greater than our input stackmemroy which is 100 (stackmemory[100]).

maybe we can do a trick on assembly language if we convert that code to assembly language then we can tackle this issue? what Im thinking is that to save the pointer of each "fi" function each recursive call by using "&" ambresend or something like that ..

what do you think?

since long time I didnt use assembly language , how we can in trivial way convert that chunk of function to assembly language?

4. I have never done any stack tracking, using the current program stack, though there may be a way to do it.

As for converting code to assembly, you can do it with "gcc -S hello.c". You can probably do this in any compiler. You would need to read the documentation for the compiler and/or IDE.

Source hello.c:
Code:
```#include <stdio.h>

int main(void)
{
printf("Hello World!\n");

return 0;
}```
Assembly hello.s:
Code:
```       .file   "hello.c"
.text
.section        .rodata
.LC0:
.string "Hello World!"
.text
.globl  main
.type   main, @function
main:
.LFB0:
.cfi_startproc
pushq   %rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
movq    %rsp, %rbp
.cfi_def_cfa_register 6
leaq    .LC0(%rip), %rax
movq    %rax, %rdi
call    puts@PLT
movl    \$0, %eax
popq    %rbp
.cfi_def_cfa 7, 8
ret
.cfi_endproc
.LFE0:
.size   main, .-main
.ident  "GCC: (Debian 13.2.0-10) 13.2.0"
.section        .note.GNU-stack,"",@progbits```

5. Originally Posted by rstanley
I have never done any stack tracking, using the current program stack, though there may be a way to do it.

As for converting code to assembly, you can do it with "gcc -S hello.c". You can probably do this in any compiler. You would need to read the documentation for the compiler and/or IDE.

Source hello.c:
Code:
```#include <stdio.h>

int main(void)
{
printf("Hello World!\n");

return 0;
}```
Assembly hello.s:
Code:
```       .file   "hello.c"
.text
.section        .rodata
.LC0:
.string "Hello World!"
.text
.globl  main
.type   main, @function
main:
.LFB0:
.cfi_startproc
pushq   %rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
movq    %rsp, %rbp
.cfi_def_cfa_register 6
leaq    .LC0(%rip), %rax
movq    %rax, %rdi
call    puts@PLT
movl    \$0, %eax
popq    %rbp
.cfi_def_cfa 7, 8
ret
.cfi_endproc
.LFE0:
.size   main, .-main
.ident  "GCC: (Debian 13.2.0-10) 13.2.0"
.section        .note.GNU-stack,"",@progbits```

I understand , thanks.
Assume that you given this challenge how you would tackle it? .. can we on C programming do like okay we already know we have only 100 bytes (stackmemory 100) so what about each function to have its addresss? got my point? like lets say f3 to have its pointer saved aside on the function itself and ask myself okay did we arrive pointer < pointer of array + 100 ? if yes then no need to call next recursion again if not then call recursive function again.

now how I can add a code for saving the pointer of the called function? like lets say I called f1 on first recursive call so I want to save function pointer itself on *p = &f1() on the caller function itself .... and so on ..

6. You should be able to view the stack through a debugger such as gdb. Check the documentation for gdb.

7. Originally Posted by rstanley
You should be able to view the stack through a debugger such as gdb. Check the documentation for gdb.
this is good thing thanks for forwarding , too much things there to read which exactly function to read there?

8. ill try my best to explain it simply while also being in depth.

tldr: use a for loop, dont worry about stack overflows.

your function in assembly & better solution
I recommend you look a godbolt or use some disassembly software to disassemble your c code. ive taken the liberty of doing it for you and commenting the disassembly so you can see what everything does.
Code:
```fn_recursion:
; prologue
push    ebp                ; save previous stack frame ( ebp )
mov     ebp, esp            ; set current stack frame base ( ebp ) to top of stack.

; if num ( arg1 ) is == 1, return
cmp     [ebp+num], 1
jz      lbl_goto_end

; if num ( arg1 ) >= 1 do processing ........
cmp     [ebp+num], 1
jge     lbl_do_processing

; return ( gets executed if num ( arg1 ) == 1 or num ( arg1 ) < 1
lbl_goto_end:
jmp     lbl_epilogue

lbl_do_processing:
mov     eax, [ebp+num]    ; mov num ( arg1 ) to eax
cdq                        ; prepare signed int in eax for division
mov     ecx, 10            ; move the divisor into ecx
idiv    ecx                ; divide the edx:eax pair by ecx

; do recursion
push    eax              ; push num ( arg1 )
call    fn_recursion        ; push return address and transfers control to fn_recursion
add     esp, 4            ; restore stack allocation ( push eax )

; epilogue
lbl_epilogue:
pop     ebp                ; restore stack frame base to previous frame
retn```
as you can see lots of stack allocations happen and the generated assembly is rather unideal as calling over and over is much slower than a simple for loop. it requires much more code and many more stack allocations than a for loop.

its much more ideal to do a simple for loop:
Code:
```void recursion(int num) {
for (; num >= 1; num /= 10) {

}
}```
which looks like:
Code:
```fn_recursion:
; prologue
push    ebp              ; save previous stack frame ( ebp )
mov     ebp, esp         ; set current stack frame base ( ebp ) to top of stack.

; start loop
jmp     lbl_do_loop

; loop code
lbl_division:
mov     eax, [ebp+num]   ; mov num ( arg1 ) to eax
cdq                      ; prepare signed int in eax for division
mov     ecx, 10          ; move the divisor into ecx
idiv    ecx              ; divide the edx:eax pair by ecx
mov     [ebp+num], eax   ; set num ( arg1 ) to divided num ( arg1 )

; handle testing condition and executing loop code
lbl_do_loop:
cmp     [ebp+num], 1   ; condition
jl      lbl_epilogue   ; if condition is met, return
jmp     lbl_division  ; if condition to return wasnt met, execute loop code

; end / return
lbl_epilogue:
pop     ebp            ; restore stack frame base to previous frame
retn```
checking for overflow & compiler code gen
checking for a stack overflow each time you call the function is also unideal as it slows down code and theoretically a stack overflow could happen anywhere in your code and is unlikely to happen in the provided code due to the small number of stack allocations. its also impossible to completely detect a stack overflow without writing a vm or making your own processor and even if one occured handling it would be pointless.

if for some reason you still wanna check manually for overflows heres how you could do that.
store top of stack in unused register, then check if the current top of stack is > than it on each recursion.
this is really annoying to implement in c however, and you be better of just using the afformentioned for loop.

getting the stack limit

windows:

on windows, you can check the stack limit via the NtThreadInformationBlock (NT_TIB)
Code:
```mov eax, fs: 0x18 ; get thread information block from fs data register
; mov eax, [eax+0x4] base of stack memory
; mov eax, [eax+0x8] limit of stack memory```
linux:
on linux you can use getrlimit ( ive never used this before and it requires allocation of stack memory to call ).

compiler generated & c runtime
generally stack overflows will be checked for automatically via compile time checks or via compiler generated code such as security cookies, chkstk, amongst other well documented means. for such crt functions you can write your own implementations to handle overflows although its not really recommended.
this code is usually generated when a large amount of data is allocated to the stack ( ex. __chkstk )

chkstk:
__chkstk Routine - Win32 apps | Microsoft Learnsecurity cookies:

9. Originally Posted by AkamiKhmenisky
this is good thing thanks for forwarding , too much things there to read which exactly function to read there?
That is your job! I can't do all the work for you! ;^)

10. Originally Posted by cuteblanket
ill try my best to explain it simply while also being in depth.

tldr: use a for loop, dont worry about stack overflows.

your function in assembly & better solution
I recommend you look a godbolt or use some disassembly software to disassemble your c code. ive taken the liberty of doing it for you and commenting the disassembly so you can see what everything does.
Code:
```fn_recursion:
; prologue
push    ebp                ; save previous stack frame ( ebp )
mov     ebp, esp            ; set current stack frame base ( ebp ) to top of stack.

; if num ( arg1 ) is == 1, return
cmp     [ebp+num], 1
jz      lbl_goto_end

; if num ( arg1 ) >= 1 do processing ........
cmp     [ebp+num], 1
jge     lbl_do_processing

; return ( gets executed if num ( arg1 ) == 1 or num ( arg1 ) < 1
lbl_goto_end:
jmp     lbl_epilogue

lbl_do_processing:
mov     eax, [ebp+num]    ; mov num ( arg1 ) to eax
cdq                        ; prepare signed int in eax for division
mov     ecx, 10            ; move the divisor into ecx
idiv    ecx                ; divide the edx:eax pair by ecx

; do recursion
push    eax              ; push num ( arg1 )
call    fn_recursion        ; push return address and transfers control to fn_recursion
add     esp, 4            ; restore stack allocation ( push eax )

; epilogue
lbl_epilogue:
pop     ebp                ; restore stack frame base to previous frame
retn```
as you can see lots of stack allocations happen and the generated assembly is rather unideal as calling over and over is much slower than a simple for loop. it requires much more code and many more stack allocations than a for loop.

its much more ideal to do a simple for loop:
Code:
```void recursion(int num) {
for (; num >= 1; num /= 10) {

}
}```
which looks like:
Code:
```fn_recursion:
; prologue
push    ebp              ; save previous stack frame ( ebp )
mov     ebp, esp         ; set current stack frame base ( ebp ) to top of stack.

; start loop
jmp     lbl_do_loop

; loop code
lbl_division:
mov     eax, [ebp+num]   ; mov num ( arg1 ) to eax
cdq                      ; prepare signed int in eax for division
mov     ecx, 10          ; move the divisor into ecx
idiv    ecx              ; divide the edx:eax pair by ecx
mov     [ebp+num], eax   ; set num ( arg1 ) to divided num ( arg1 )

; handle testing condition and executing loop code
lbl_do_loop:
cmp     [ebp+num], 1   ; condition
jl      lbl_epilogue   ; if condition is met, return
jmp     lbl_division  ; if condition to return wasnt met, execute loop code

; end / return
lbl_epilogue:
pop     ebp            ; restore stack frame base to previous frame
retn```
checking for overflow & compiler code gen
checking for a stack overflow each time you call the function is also unideal as it slows down code and theoretically a stack overflow could happen anywhere in your code and is unlikely to happen in the provided code due to the small number of stack allocations. its also impossible to completely detect a stack overflow without writing a vm or making your own processor and even if one occured handling it would be pointless.

if for some reason you still wanna check manually for overflows heres how you could do that.
store top of stack in unused register, then check if the current top of stack is > than it on each recursion.
this is really annoying to implement in c however, and you be better of just using the afformentioned for loop.

getting the stack limit

windows:

on windows, you can check the stack limit via the NtThreadInformationBlock (NT_TIB)
Code:
```mov eax, fs: 0x18 ; get thread information block from fs data register
; mov eax, [eax+0x4] base of stack memory
; mov eax, [eax+0x8] limit of stack memory```
linux:
on linux you can use getrlimit ( ive never used this before and it requires allocation of stack memory to call ).

compiler generated & c runtime
generally stack overflows will be checked for automatically via compile time checks or via compiler generated code such as security cookies, chkstk, amongst other well documented means. for such crt functions you can write your own implementations to handle overflows although its not really recommended.
this code is usually generated when a large amount of data is allocated to the stack ( ex. __chkstk )

chkstk:
__chkstk Routine - Win32 apps | Microsoft Learnsecurity cookies:

First off thanks much for your effort , I understand .
but again I think what Im asking is more simply than what you're trying to asnwer.

assume it's given that you have int stackmemory[100] which is your stack memory that's handling all your recursive / functions / calls / local parameters / ..etc.

now assume for each call of recursive call we will occupy 20bytes lets say. now my concern is that assume you input to function 1000000 value so you know each time you divide by 10 means that we call the function again that means total occupation from stack memory is 6 (6 times function called)*20 then on our case its 120 so it's greater than 100 because stackmemory is 100 ( stackmemory[100] ) then stackover flow happens because on 6th called function we exceeded maximal size of our stack which is 100 on our case.

Now how I can prevent that from happening and to add a condition to the function to be safety in terms of stack memory allocation? meaning like to check that condition first if enough memory left then we can go to next recursive function , else recursive stop.

what I was thinking about is to save the pointer of each called function aside and to verify it's not reached the maximal memory allocation pointer ... ? got my point ..

assume you have given stackmemory[100] with its address start .. or actually its address is stackmemory pointer itself .

11. When we run a compiler is actually telling us that there is stackover flow so this I know , but challenge is to code some thing and same purpose manually and on trivial way for stackover flow sanity check instead of compiler doing that ..

12. Originally Posted by AkamiKhmenisky
When we run a compiler is actually telling us that there is stackover flow so this I know , but challenge is to code some thing and same purpose manually and on trivial way for stackover flow sanity check instead of compiler doing that ..
Take a look at this page: Use compiler flags for stack protection in GCC and Clang | Red Hat Developer

13. Originally Posted by rstanley
thanks much actually I found something on internet which is really good , its simple solution for detecting stackoverflow within given size before stackover flow happens.

Code:
```unsigned int get_stack_address( void )
{
unsigned int r = 0;
__asm mov dword ptr [r], esp;
return r;
}
void rec( int x, const unsigned int begin_address )
{
// here just put 100 000 bytes of memory
{
//std::cout << "Recursion level " << x << " stack too high" << std::endl;
return;
}
rec( x + 1, begin_address );
}
int main( void )
{
int x = 0;
}```

I understand the logic here but this row code not getting it properly :
Code:
` __asm mov dword ptr [r], esp;`

thanks much!

14. I am away from my computer for the rest of the day. Perhaps someone else can assist you further.

15. Originally Posted by AkamiKhmenisky
thanks much actually I found something on internet which is really good , its simple solution for detecting stackoverflow within given size before stackover flow happens.

Code:
```unsigned int get_stack_address( void )
{
unsigned int r = 0;
__asm mov dword ptr [r], esp;
return r;
}
void rec( int x, const unsigned int begin_address )
{
// here just put 100 000 bytes of memory
{
//std::cout << "Recursion level " << x << " stack too high" << std::endl;
return;
}
rec( x + 1, begin_address );
}
int main( void )
{
int x = 0;
}```

I understand the logic here but this row code not getting it properly :
Code:
` __asm mov dword ptr [r], esp;`