every C learner's nightmare #2: recursion

Hi all.

Can someone please explain how this program works?

1. How are multiple instances of c preserved? Where are the multiple values stored?
2. How can putchar() print out all the multiple values of c without some type of loop? How is it accessing the values of c?

I don't know how this can be done without some type of array. Very baffling. Thanks in advance.

Code:

#include <stdio.h>

void wrt_it(void);

int main(void)
{
    printf("Input a line: ");
    wrt_it();
    printf("\n\n");

    return 0;
}

void wrt_it(void)
{
    int c;

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

Output.

Code:

Input a line: Hello World

dlroW olleH

The loop is implied in the fact the function is calling itself, when some condition ((c = getchar) != '\n') is true. Each type wrt_it() is called, a new instance of c is created, otherwise the code continues on to the putchar() call. This keeps happening until input has a '\n'. Then the '\n' is output (the first time putchar() is called). Then wrt_it() returns .... to the wrt_it() that had read the 'd', so 'd' is output. This continues, so putchar() is called for each character, in reverse order.


Please cease and desist with labeling your threads as "every C learner's worst nightmare". You're assuming that everyone has the same basic challenges learning C that you do, which is simply not true. In practice, different people find different things challenging. So your approach comes across as unnecessarily and annoyingly childish.

Every time the recursion happens, that's a loop. The values are saved in the area called the "stack". Every time you recurse, you use a deeper level of the stack, (this movement is called a "push"), and every time you return from a recursion, you "pop" up one level in the stack.

Some logic works really well with this kind of usage of the stack. Recursive programs are generally much shorter and intuitive as you read the code. Quicksort and depth first search are two famous recursive algorithms.

One problem is that the size of the stack is rather small, so although it's usually adequate, it's very possible to exceed it's size, and wreck your programs run.

What adak said is why the word is printed in reverse.Remember that stack is a LIFO(Last In First Out) struct.So at the bottom of the stack you have the H and at the top of it you have te \n.So when recursion calls are terminated(yes,this happens when c is \n),then the putchar is going to be executed.So first it changes line,as you should have observed,and then prints the letters that are stored in the stack.

I advice you to take a good look into recursion,because it can become a powerful tool for us.Don't get upset,getting experience in it will explain everything to you.

Recursion was/is my nightmare too

This program simply reverse anything you write before you hit enter.
-To understand recursive function, you need have know of what local(automatic variable) is. A local variable can exist only inside the one particular function.
-Though there is only one user-function wrt_it() in your program. Calling wrt_it() function from same function, makes a wrt_it() to call wrt_it(). But, you shouldn't assume these two functions are same though their name is. These two wrt_it() are different functions.

Explanation of the code
You have called wrt_it() function from main() function. The control of the program will jump to wrt_it(). It has a local variable c of integer type. If c is any other character than '\n' (new line character), wrt_it() will call itself again. Suppose, you have entered abc. Since, 'a' is not a equal to '\n', wrt_it() will call itself. This wrt_it() function is different function than the previous wrt_it() from which it was called. It has a local variable c of integer type. Since, local variable are local to particular function only, you must not assume, the c variable before and this c variable are same because, these variable are inside two different wrt_it() function. Similarly, this process goes on and variables are stored in form of stack untill variable c equals to '\n'.
Suppose you have typed abc and pressed enter. Variable c of first wrt_it() function stores character 'a'. Variable c of second wrt_it() function stores character 'b'. Variable c of third wrt_it() function stores character 'c'. Variable c of fourth wrt_it() function stores character '\n'. When, c becomes '\n', test condition (c=getchar()!='\n') will be false. Then, the fourth function wrt_it() will print '\n' character first. Then, fourth wrt_it() returns to the third wrt_it(), prints 'c'. Similarly, third_wrt() returns to second wrt_it() and prints 'b' and Second wrt_it() returns to first wrt_it() and prints 'a'. Thus the output will be cba.
Notice that, when your input is 'abc' then pressed enter. There will be gap of 1 line between them because, the first character it prints is '\n' then, only it prints 'cba'.
I hope this will help you. If you are still confused with local variable and recursive function. Visit: local variable to learn about local variables in C programming.

Learn more about recursive function: Recursive function in C programming

programiz made a nice explanation.However,a friendly tip do not reproduce by accident what has already been said before.Try to add only new information in your post.Why?Because ,this way you help the person who asked the question a lot more than you think and others that may be reading the thread too(e.g. me :-p )

Also for cfanatic mind that if you want the c to be the same exact value in every function call,this is possible with static keyword,but this is not what you need now -i am just saying it for future use -

Originally Posted by std10093

Also for cfanatic mind that if you want the c to be the same exact value in every function call,this is possible with static keyword,but this is not what you need now -i am just saying it for future use -

I think you're confusing static with const. static is kind of the swiss army knife of C, but here it is mutable and static would only increase the lifetime of 'c`.

Actually i did not confuse them,but i made a mistake in the following

Code:

Also for cfanatic mind that if you want the c to be the same exact value in every function call,this is possible with static keyword

Let me try again

In recursion,because as well said before,every function call of the recursive function is a different function(even though they have the same name),all the local variables are re-created(memory is allocated for every local variable when the function is initiated and this memory is de-allocated when the function is been terminated).As a result the local variable c for example,can not keep track if there was another c variable playing the same role before her(so of course it can not know her value) and can not foresight if there is going to be another c variable that has the same role as her.So by adding the key word "static" ,you achieve the fact that you made your local variable immortal.In other words,it will remember the value that it had in the previous call of the function(except it is the 1st function call,so no history to remember),and when-for instance-the function is called for second time,when the function starts the static local variable will have the vary same value as the one it had on the first function call. cfanatic if you wish,i can make a simple example for you

So if you want this local variable to maintain the same value among all the function calls of the function that is the variable's world,then you should make the variable immortal (static ) and const (const won't allow any variable to re-set it's value (as a result it has to be initialized when declared ) )

Thanks whiteflag for your input

Recursion is actualy really easy. As long as you understand functions, then you can just think of it like this:

Code:

#include <stdio.h>

void wrt_it(void);
void wrt_it2(void);
void wrt_it3(void);
void wrt_it4(void);
void wrt_it5(void);
// ...

int main(void)
{
    printf("Input a line: ");
    wrt_it();
    printf("\n\n");

    return 0;
}

void wrt_it(void)
{
    int c;
    if((c = getchar()) != '\n')
        wrt_it2();
    putchar(c);
}
void wrt_it2(void)
{
    int c;
    if((c = getchar()) != '\n')
        wrt_it3();
    putchar(c);
}
void wrt_it3(void)
{
    int c;
    if((c = getchar()) != '\n')
        wrt_it4();
    putchar(c);
}
void wrt_it4(void)
{
    int c;
    if((c = getchar()) != '\n')
        wrt_it5();
    putchar(c);
}
void wrt_it5(void)
{
    int c;
    if((c = getchar()) != '\n')
        wrt_it6();
    putchar(c);
}
// ...

Now I understand recursion much better. Thanks for the awesome replies.

Originally Posted by cfanatic

Now I understand recursion much better.

Glad to hear that Mark