Stack & recursion Question

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?

re: Stack & recursion Question

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.

re: Stack & recursion Question

"herrcho" <herrcho2803@kornet.net> schrieb im Newsbeitrag
news:blgi36$sff$1@news1.kornet.net...[color=blue]
> 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?[/color]

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

re: Stack & recursion Question

herrcho wrote:[color=blue]
>
> 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?[/color]

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...ogs/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
jvn@lessspamformother.virginia.edu
^^^^^^^^^^^^^^^^^^
http://galileo.phys.virginia.edu/~jvn/

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

re: Stack & recursion Question

Julian V. Noble wrote:
[color=blue]
> herrcho wrote:[color=green]
>>
>> 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?[/color]
>
> Let me recommend my column on this subject from "Computing in
> Science and Engineering". Title is "Recurses!" Can be found at
>
>[/color]
http://www.phys.virginia.edu/classes...ogs/Cprogs.htm[color=blue]
>
> 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.)
>[/color]

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

--
Fifth Law of Procrastination:
Procrastination avoids boredom; one never has the feeling that
there is nothing important to do.

re: Stack & recursion Question

On Thu, 02 Oct 2003 19:02:35 -0400, bd wrote:
[color=blue]
> Julian V. Noble wrote:
>[color=green]
>> 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.[/color]
>
> Dosen't Continuation Passing Style not use a stack? Or am I confused
> about it?[/color]

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