rohitdivas
asked on
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
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
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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)
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)
Just like the old-fashioned HP-calculators, with RPN.
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....
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....
I was already wondering... Points to Mercantilum!
ASKER
i hope this will be acceptable to u know sunnycoder
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.
"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.
ASKER
Please accept ur comment as answer and close this question. i got the concept behind my query.
ASKER
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
I am sorry for my behaviour. Please do this favour for me by selecting all the open question I have.
Regards,
Rohit
thanks for the correction AnnieMod :o)
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.