Go Premium for a chance to win a PS4. Enter to Win

x
?
Solved

Stack and Recursion!!

Posted on 2004-04-21
15
Medium Priority
?
827 Views
Last Modified: 2010-04-15
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
0
Comment
Question by:rohitdivas
  • 3
  • 3
  • 2
  • +2
15 Comments
 
LVL 45

Accepted Solution

by:
sunnycoder earned 150 total points
ID: 10885924
Hi rohitdivas,

f(5)
 return f(4) +5;
        return f(3) +4;  
               return f(2) +3;
                      return f(1) +2;
                             return f(0) +1;
                                    return 1

this will be the max stack for the call ... now unwind it to get the value

Sunnycoder
0
 
LVL 9

Expert Comment

by:ankuratvb
ID: 10886177
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.
0
 
LVL 10

Expert Comment

by:Mercantilum
ID: 10886456
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)
0
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
LVL 46

Expert Comment

by:Sjef Bosman
ID: 10886664
Just like the old-fashioned HP-calculators, with RPN.
0
 
LVL 9

Expert Comment

by:ankuratvb
ID: 10886939
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....
0
 
LVL 46

Expert Comment

by:Sjef Bosman
ID: 10887026
I was already wondering... Points to Mercantilum!
0
 

Author Comment

by:rohitdivas
ID: 10887047
i hope this will be acceptable to u know sunnycoder
0
 
LVL 9

Expert Comment

by:ankuratvb
ID: 10887177
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.

0
 

Author Comment

by:rohitdivas
ID: 10887227
Please accept ur comment as answer and close this question. i got the concept behind my query.
0
 

Author Comment

by:rohitdivas
ID: 10896170
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
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 10915691
thanks for the correction AnnieMod :o)
0

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.

926 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question