Go Premium for a chance to win a PS4. Enter to Win

x
Solved

# Stack and Recursion!!

Posted on 2004-04-21
Medium Priority
827 Views
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
0
Question by:rohitdivas
• 3
• 3
• 2
• +2

LVL 45

Accepted Solution

sunnycoder earned 150 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

ID: 10886177

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

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

ID: 10886664
Just like the old-fashioned HP-calculators, with RPN.
0

LVL 9

Expert Comment

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

LVL 46

Expert Comment

ID: 10887026
I was already wondering... Points to Mercantilum!
0

Author Comment

ID: 10887047
i hope this will be acceptable to u know sunnycoder
0

LVL 9

Expert Comment

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

ID: 10887227
Please accept ur comment as answer and close this question. i got the concept behind my query.
0

Author Comment

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

ID: 10915691
thanks for the correction AnnieMod :o)
0

## Featured Post

Question has a verified solution.

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

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â€¦
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see soâ€¦
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.
###### Suggested Courses
Course of the Month9 days, 18 hours left to enroll