Link to home
Start Free TrialLog in
Avatar of rohitdivas
rohitdivas

asked on

Stack and Recursion!!

Dear All,

Can some body explain the detail concept of recursion and solution to the below problem

I need to know how the values are built on the  stack and how the compiler manage it.
////////////
#include <stdio.h>

int f(int x) {
if(x<=0)
return 1;
return f(x-1) +x;
}

void main() {
printf("%d",f(5));
}
/////////////
Please feel free for asking further clarifications in this regards,
Rohit
ASKER CERTIFIED SOLUTION
Avatar of sunnycoder
sunnycoder
Flag of India image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Adding to Sunny's post:

f(0)=1;

f(5)//f(5)=16
return f(4) +5;//f(4)=7+4=11;
       return f(3) +4;//f(3)=4+3=7;  
              return f(2) +3;//f(2)=2+2=4;
                     return f(1) +2;//f(1)=1+1=2;
                            return f(0)+1;
                                   return 1 //f(0)=1

Going from Botttom up.
To answer all your questions, actually the compiler does not do any special treatment to a recursive function.

The way a function with a parameter returning a data works is:  (case of  int f(int x) )
(assuming you know what means push and pop to / from the stack)

   push (parameter)
   y = call f
   pop ()  // the parameter, to get stack in the same state as before the call

f does: it will return a value in a register, let say it keeps the value in a temp space called 'y'

    (Assuming an increasing stack. Before a push(x), stack pointer index is N, after a push, it's N+2 for instance. So to get the 'x' you have to peek
     value at stack_index-2)

   push (y)  // actually create a space in stack to put the temp. variable y, e.g current stack_index(-2)
   use parameter value in stack as 'x', e.g. stack_index(-4), since it was pushed before...
   y = pop()  // get value in a register of y
   return y  // via a register etc..

Actually the  call and return use the stack. Call f is actually
    push(return address of the current location in my program)
    call f
   (when f returns, it uses the address pushed previously to back to the next instruction after the initial call)
This is true for each call of f ; since f is recursive, we'll have (increasing stack...)
    push parameter, stack pointer => N+2
    push(return address of the current location in my main function), stack_pointer is N+4
    call f (when f returns, it uses the address pushed previously at N+2)
    pop (parameter pushes at N)

But let's not make heavier the reading ot this ...
   

e.g. for f(5):
main:
   push(5)
   result = call f
   pop()
 
In the case of your recursive call, what happens:
(y is the local refence to temp. variable for result, each call to f will have its  "own" y, being always the same index is stack, which is growing...
It is for each call to f,  stack_index(-2))

    push(5)     // main
    y = call f    // main
        push(y) // space for local temp. variable
        push(4)
        y = call f
            push(y) // space for local temp. variable
            push(3)
            y = call f
               push(y) // space for local temp. variable
               push(2)
               y = call f
                  push(y) // space for local temp. variable
                  push(1)
                  y = call f
                     push(y) // space for local temp. variable
                     push(0)
                     y = call f
                        push(y) // space for local temp. variable
                        y = 1, since x == 0 in stack
                        pop() // for y
                        return (y value) // return 1
                     pop() // remove the x (0)
                     pop() // remove the temp y
                     return (y+x) // return result of call to f + x, e.g.  1+1 = 2
                  pop() // remove the x (1)
                  pop() // remove the temp y
                  return (y+x) // return result of call to f + x, e.g.  2+2 = 4
               pop() // remove the x (2)
               pop() // remove the temp y
               return (y+x) // return result of call to f + x, e.g.  4+3 = 7
            pop() // remove the x (3)
            pop() // remove the temp y
            return (y+x) // return result of call to f + x, e.g. 7+4 = 11
         pop() // remove the x (4)
         pop() // remove the temp y
         return (y+x) // return result of call to f + x, e.g. 11+5 = 16
      pop () // main: remove the x (5)
      result = return value (16)
Just like the old-fashioned HP-calculators, with RPN.
Thats weird.

Question:Can some body explain the detail concept of recursion and solution to the below problem
I need to know how the values are built on the  stack and how the compiler manage it.

Solution:"Just like the old-fashioned HP-calculators, with RPN. "

Hmmm....
I was already wondering... Points to Mercantilum!
Avatar of rohitdivas
rohitdivas

ASKER

i hope this will be acceptable to u know sunnycoder
I thought Mercantilum gave you the best answer to:

"the detail concept of recursion and solution to the below problem"
and
"I need to know how the values are built on the  stack and how the compiler manage it."

I barely explained what Sunny had previously said.

Please accept ur comment as answer and close this question. i got the concept behind my query.
Dear ee_ai_construct,
I am sorry for my behaviour. Please do this favour for me by selecting all the open question I have.
Regards,
Rohit
thanks for the correction AnnieMod :o)