Thread: 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.

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?

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

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:
__security_init_cookie | Microsoft Learn

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:
__security_init_cookie | Microsoft Learn

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 .