Improve company productivity with a Business Account.Sign Up

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 829
  • Last Modified:

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
0
rohitdivas
Asked:
rohitdivas
  • 3
  • 3
  • 2
  • +2
1 Solution
 
sunnycoderCommented:
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
 
ankuratvbCommented:
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
 
MercantilumCommented:
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 Kind of Coding Program is Right for You?

There are many ways to learn to code these days. From coding bootcamps like Flatiron School to online courses to totally free beginner resources. The best way to learn to code depends on many factors, but the most important one is you. See what course is best for you.

 
Sjef BosmanGroupware ConsultantCommented:
Just like the old-fashioned HP-calculators, with RPN.
0
 
ankuratvbCommented:
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
 
Sjef BosmanGroupware ConsultantCommented:
I was already wondering... Points to Mercantilum!
0
 
rohitdivasAuthor Commented:
i hope this will be acceptable to u know sunnycoder
0
 
ankuratvbCommented:
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
 
rohitdivasAuthor Commented:
Please accept ur comment as answer and close this question. i got the concept behind my query.
0
 
rohitdivasAuthor Commented:
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
 
sunnycoderCommented:
thanks for the correction AnnieMod :o)
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

What Kind of Coding Program is Right for You?

There are many ways to learn to code these days. From coding bootcamps like Flatiron School to online courses to totally free beginner resources. The best way to learn to code depends on many factors, but the most important one is you. See what course is best for you.

  • 3
  • 3
  • 2
  • +2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now