Thread: Recursion && given stack memory challenge.

  1. #1
    Registered User
    Join Date
    Jan 2024
    Posts
    25

    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.
    Last edited by AkamiKhmenisky; 01-25-2024 at 04:23 AM.

  2. #2
    Registered User rstanley's Avatar
    Join Date
    Jun 2014
    Location
    New York, NY
    Posts
    1,110
    Quote Originally Posted by AkamiKhmenisky View Post
    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. #3
    Registered User
    Join Date
    Jan 2024
    Posts
    25
    Quote Originally Posted by rstanley View Post
    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?
    Last edited by AkamiKhmenisky; 01-25-2024 at 06:28 AM.

  4. #4
    Registered User rstanley's Avatar
    Join Date
    Jun 2014
    Location
    New York, NY
    Posts
    1,110
    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
    Last edited by rstanley; 01-25-2024 at 06:44 AM.

  5. #5
    Registered User
    Join Date
    Jan 2024
    Posts
    25
    Quote Originally Posted by rstanley View Post
    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. #6
    Registered User rstanley's Avatar
    Join Date
    Jun 2014
    Location
    New York, NY
    Posts
    1,110
    You should be able to view the stack through a debugger such as gdb. Check the documentation for gdb.

  7. #7
    Registered User
    Join Date
    Jan 2024
    Posts
    25
    Quote Originally Posted by rstanley View Post
    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. #8
    Registered User
    Join Date
    Jan 2024
    Posts
    3
    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
    Last edited by cuteblanket; 01-25-2024 at 07:06 AM.

  9. #9
    Registered User rstanley's Avatar
    Join Date
    Jun 2014
    Location
    New York, NY
    Posts
    1,110
    Quote Originally Posted by AkamiKhmenisky View Post
    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. #10
    Registered User
    Join Date
    Jan 2024
    Posts
    25
    Quote Originally Posted by cuteblanket View Post
    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 .
    Last edited by AkamiKhmenisky; 01-25-2024 at 07:23 AM.

  11. #11
    Registered User
    Join Date
    Jan 2024
    Posts
    25
    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. #12
    Registered User rstanley's Avatar
    Join Date
    Jun 2014
    Location
    New York, NY
    Posts
    1,110
    Quote Originally Posted by AkamiKhmenisky View Post
    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. #13
    Registered User
    Join Date
    Jan 2024
    Posts
    25
    Quote Originally Posted by rstanley View Post
    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.

    see here please :

    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
        if ( begin_address - get_stack_address() > 100000 )
        {
            //std::cout << "Recursion level " << x << " stack too high" << std::endl;
            return;
        }
        rec( x + 1, begin_address );
    }
    int main( void )
    {
        int x = 0;
        rec(x,get_stack_address());
    }

    I understand the logic here but this row code not getting it properly :
    Code:
     __asm mov dword ptr [r], esp;
    , any help please about what this exactly row code doing?


    thanks much!

  14. #14
    Registered User rstanley's Avatar
    Join Date
    Jun 2014
    Location
    New York, NY
    Posts
    1,110
    I am away from my computer for the rest of the day. Perhaps someone else can assist you further.

  15. #15
    Registered User rstanley's Avatar
    Join Date
    Jun 2014
    Location
    New York, NY
    Posts
    1,110
    Quote Originally Posted by AkamiKhmenisky View Post
    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.

    see here please :

    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
        if ( begin_address - get_stack_address() > 100000 )
        {
            //std::cout << "Recursion level " << x << " stack too high" << std::endl;
            return;
        }
        rec( x + 1, begin_address );
    }
    int main( void )
    {
        int x = 0;
        rec(x,get_stack_address());
    }

    I understand the logic here but this row code not getting it properly :
    Code:
     __asm mov dword ptr [r], esp;
    , any help please about what this exactly row code doing?


    thanks much!
    I would avoid assembler code completely and see if the article I gave you has a better solution for your needs.
    IMHO!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. recursion and stack - trying to understand
    By bos1234 in forum C Programming
    Replies: 2
    Last Post: 09-01-2013, 01:58 AM
  2. Replies: 9
    Last Post: 04-29-2011, 09:26 AM
  3. Stack overflow in recursion
    By Nom1fan in forum C Programming
    Replies: 4
    Last Post: 11-24-2010, 12:51 PM
  4. Callback recursion: stack overflow
    By nicoqwertyu in forum C++ Programming
    Replies: 8
    Last Post: 03-16-2010, 11:09 AM
  5. stack and recursion help needed!
    By LouB in forum C++ Programming
    Replies: 3
    Last Post: 07-01-2002, 02:19 PM

Tags for this Thread