Stack & recursion Question

[herrcho]

int main()
{
printf("Input a line: ");
wrt_it();
printf("\n\n");
return 0;
}

void wrt_it()
{
int c;

if (( c = getchar()) != '\n')
wrt_it();
putchar(c);
}

the above is from 'A book on C'
and it says the function calls are stacked.

i know what stack means. but don't understand how stack is related to
recursion.

Could anyone explain to me about that ? and, why does the input
characters print reversely?

 

[Kyle S. Shim]

Stack is the memory portion which linker determines for the executable to
use. It's the place for arguments, return address and local variables when a
function is called.

: i know what stack means. but don't understand how stack is related to
: recursion.

Your program comsumes stack space every time functions are called.

: Could anyone explain to me about that ? and, why does the input
: characters print reversely?

Think about the way how the function is called. A debugger may help you.

 

[Robert Stankowic]

int main()
{
printf("Input a line: ");
wrt_it();
printf("\n\n");
return 0;
}

void wrt_it()
{
int c;

if (( c = getchar()) != '\n')
wrt_it();
putchar(c);
}

the above is from 'A book on C'
and it says the function calls are stacked.

i know what stack means. but don't understand how stack is related to
recursion.

Could anyone explain to me about that ? and, why does the input
characters print reversely?

First: the language does not say anything about how parameters are passed.
Fortunately your book says " function calls are stacked", which IMHO has not
necessarily to do with a "stack" like it is used in many, but not all
implementations.
Anyway, parameters must be stored in a last in first out way somehow...

now to your question:
void wrt_it()
{
int c;

if (( c = getchar()) != '\n')
wrt_it();
putchar(c);
}
wrt_it is called from main(), it gets a local copy of c
wrt_it receives one character and stores it in c
let's assume it is not '\n' then
wrt_it calls itself, this new instance gets it's own local copy of
c, to help understanding let's name it c1
wrt_it receives one character and stores it in c1
let's assume it is not '\n' then
wrt_it calls itself, this new instance gets it's own local
copy of c, to help understanding let's name it c2
wrt_it receives one character and stores it in c2
let's assume it is '\n' now, then
wrt_it does not call itself anymore, instead it outputs it's
copy of c (c2)
and returns to the previous instance of itself
the previous instance also outputs _it's_c which is c1 and
returns to the previous instance of itself
this instance again outputs it's own copy of c and returns to the
caller (main() in our example
we are done

Ngngng - hope I got it right (including the formatting)
Robert

 

[Julian V. Noble]

int main()
{
printf("Input a line: ");
wrt_it();
printf("\n\n");
return 0;
}

void wrt_it()
{
int c;

if (( c = getchar()) != '\n')
wrt_it();
putchar(c);
}

the above is from 'A book on C'
and it says the function calls are stacked.

i know what stack means. but don't understand how stack is related to
recursion.

Could anyone explain to me about that ? and, why does the input
characters print reversely?

Let me recommend my column on this subject from "Computing in
Science and Engineering". Title is "Recurses!" Can be found at

http://www.phys.virginia.edu/classes/551.jvn.fall01/CiSE_progs/Cprogs.htm

Basically, languages that implement recursion use stacks to pass
parameters and return addresses when calling subroutines (or functions).
How this is done, exactly, is left up to the implementer. But a stack
of some sort must be used for recursion. (It may or may not be the cpu
stack, depending on the cpu, etc.)

--
Julian V. Noble
Professor Emeritus of Physics
(e-mail address removed)
^^^^^^^^^^^^^^^^^^
http://galileo.phys.virginia.edu/~jvn/

"Science knows only one commandment: contribute to science."
-- Bertolt Brecht, "Galileo".

 

[bd]

Let me recommend my column on this subject from "Computing in
Science and Engineering". Title is "Recurses!" Can be found at

http://www.phys.virginia.edu/classes/551.jvn.fall01/CiSE_progs/Cprogs.htm

Basically, languages that implement recursion use stacks to pass
parameters and return addresses when calling subroutines (or functions).
How this is done, exactly, is left up to the implementer. But a stack
of some sort must be used for recursion. (It may or may not be the cpu
stack, depending on the cpu, etc.)

Dosen't Continuation Passing Style not use a stack? Or am I confused about
it?

 

[Sheldon Simms]

Dosen't Continuation Passing Style not use a stack? Or am I confused
about it?

CPS uses a continuation, which grows until it is executed.

What's important is that tail-recursive calls don't have to grow
the stack. A tail-recursive function in C might well blow the
stack, but that's a problem with the implementation, not a problem
with recursion.

-Sheldon