Solved

Stack and Recursion!!

Posted on 2004-04-21
15
819 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
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
 
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
Microsoft Certification Exam 74-409

Veeam® is happy to provide the Microsoft community with a study guide prepared by MVP and MCT, Orin Thomas. This guide will take you through each of the exam objectives, helping you to prepare for and pass the examination.

 
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

Are your AD admin tools letting you down?

Managing Active Directory can get complicated.  Often, the native tools for managing AD are just not up to the task.  The largest Active Directory installations in the world have relied on one tool to manage their day-to-day administration tasks: Hyena. Start your trial today.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
c++ substatte a varabe for a string in a LPCTSTR statment 8 83
Global Keyboard Hooks Blocked 4 70
Raspberry Pi 3 to send text message 9 73
Resolve Dependency Issues 4 45
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…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
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.

910 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

23 Experts available now in Live!

Get 1:1 Help Now