• C

# 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));
}
/////////////
Rohit
###### Who is Participating?

Commented:
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

Commented:

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

Commented:
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

Groupware ConsultantCommented:
Just like the old-fashioned HP-calculators, with RPN.
0

Commented:
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

Groupware ConsultantCommented:
I was already wondering... Points to Mercantilum!
0

Author Commented:
i hope this will be acceptable to u know sunnycoder
0

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

Author 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

Commented:
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.