Solved

Stack and Recursion!!

Posted on 2004-04-21
15
818 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 50 total points
Comment Utility
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
Comment Utility
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
Comment Utility
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
 
LVL 46

Expert Comment

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

Expert Comment

by:ankuratvb
Comment Utility
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
What Is Threat Intelligence?

Threat intelligence is often discussed, but rarely understood. Starting with a precise definition, along with clear business goals, is essential.

 
LVL 46

Expert Comment

by:Sjef Bosman
Comment Utility
I was already wondering... Points to Mercantilum!
0
 

Author Comment

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

Expert Comment

by:ankuratvb
Comment Utility
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
Comment Utility
Please accept ur comment as answer and close this question. i got the concept behind my query.
0
 

Author Comment

by:rohitdivas
Comment Utility
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
Comment Utility
thanks for the correction AnnieMod :o)
0

Featured Post

Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
Estimate porting issues. 9 116
Finding a good hash function 4 116
Socket Programming (Unix) 8 98
valid enum? 6 67
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.

771 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

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now