Thread: every C learner's nightmare #2: recursion

  1. #1
    Registered User
    Join Date
    Jul 2012
    Location
    Australia
    Posts
    242

    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
    Last edited by cfanatic; 09-21-2012 at 11:44 PM.
    IDE: Code::Blocks | Compiler Suite for Windows: TDM-GCC (MingW, gdb)

  2. #2
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    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.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  4. #4
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    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

  5. #5
    Registered User
    Join Date
    May 2012
    Location
    Kathmandu
    Posts
    4
    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

  6. #6
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    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 -

  7. #7
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Quote Originally Posted by std10093 View Post
    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`.

  8. #8
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    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

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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);
    }
    // ...
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #10
    Registered User
    Join Date
    Jul 2012
    Location
    Australia
    Posts
    242
    Now I understand recursion much better. Thanks for the awesome replies.
    IDE: Code::Blocks | Compiler Suite for Windows: TDM-GCC (MingW, gdb)

  11. #11
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Quote Originally Posted by cfanatic View Post
    Now I understand recursion much better.
    Glad to hear that Mark

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. every C learner's nightmare: linked lists
    By cfanatic in forum C Programming
    Replies: 8
    Last Post: 09-21-2012, 06:58 PM
  2. Xcode, Mac or Me??? Learner Question
    By Mr1ncognit0 in forum C++ Programming
    Replies: 5
    Last Post: 01-15-2012, 02:20 PM
  3. New learner Help!
    By 2001beibei in forum C Programming
    Replies: 2
    Last Post: 06-02-2008, 09:06 AM
  4. Help for the learner
    By inmaterichard in forum Game Programming
    Replies: 3
    Last Post: 08-16-2007, 12:55 AM
  5. Learner...
    By Hugo716 in forum C++ Programming
    Replies: 13
    Last Post: 04-21-2006, 03:04 PM