CODEWITHSUNDEEP
recursion
Ruchir
Ruchir

Reputation: 1068

In Recursion factorial program when a function is returning how stack FRAMES are maintained?

Ex : Function Implementation:

 facto(x){
     if(x==1){ 
             return 1;
      }
      else{ 
           return x*facto(x-1); 
     }

in more simple way lets take a stack -->

        returns
 |2(1)|---->    2(1) evaluates to 2
 |3(2)|---->    3(2)<______________| evaluates to 6
 |4(3)|---->    4(6)<______________| evaluates to 24
 |5(4)|---->    5*(24)<____________| evaluates to 120
 ------         finally back to main...

when a function returns in reverse manner it never knows what exactly is behind it? The stack have activation records stored inside it but how they know about each other who is popped and who is on top? How the stack keeps track of all variables within the function being executed? Besides this, how it keeps track of what code is executed (stackpointer)? When returning from a function call the result of that function will be filled in a placeholder. By using the stackpointer but how it knows where to continue executing code? These are the basics of how the stack works I know but for recursion I don't understand how it exactly works??

Upvotes: 0

Views: 253

Answers (1)

Fernando
Fernando

Reputation: 1450

When a function returns its stack frame is discarded (i.e the complete local state is pop-ed out of the stack).

The details depend on the processor architecture and language.

Check the C calling conventions for x86 processors: http://en.wikipedia.org/wiki/X86_calling_conventions, http://en.wikibooks.org/wiki/X86_Disassembly/Functions_and_Stack_Frames and search for "PC Assembly Language" by Paul A. Carter (its a bit outdated but it has a good explanation of C and Pascal calling conventions for the ia32 architecture).

In C in x86 processors:

a. The calling function pushes the parameters of the called function to the stack in reverse order and then it pushes the pointer to the return address.

push -6
push 2
call add     # pushes `end:` address an then jumps to `add:` (add(2, -6))
end:
# ...

b. Then the called function pushes the base of the stack (the ebp register in ia32) (it is used to reference local variables in the caller function).

add:
push ebp

c. The called function sets ebp to the current stack pointer (this ebp will be the reference to access the local variables and parameters of the current function instance).

add:
# ...
mov ebp, esp

d. The called function reserves space in the stack for the local (automatic) variables subtracting the size of the variables to the stack pointer.

add:
# ...
sub esp, 4     # Reserves 4 bytes for a variable

e. At the end of the called function it sets the stack pointer to be ebp (i.e frees its local variables), restores the ebp register of the caller function and returns to the return address (previously pushed by the caller).

add:
# ...
mov esp, ebp  # frees local variables
pop ebp       # restores old ebp
ret           # pops `end:` and jumps there

f. Finally the caller adds to the stack pointer the space used by the parameters of the called function (i.e frees the space used by the arguments).

# ...
end:
add esp, 8

Return values (unless they are bigger than the register) are returned in the eax register.

Upvotes: 1

Related Questions