Explaining needed C recursion

Question

I need some help with this particular code. I do not really understand it to its fullest. Could someone take the time and explain it to me? What it does is take a word and prints out its reverse. I don't understand the recursion part though, for n=1 the for loop will only run once, and the recursion will run until it reads the whole word and it meets the ' ' mark, but then how does it print out the reversed word?

 void reverse()
 {
   char c;
   scanf("%c", &c);
   if (c!=' ')
       {
        reverse();
       }
 printf("%c", c);
 }


 int main()
 {
 int n, i;
 printf("\nThe number of the words=");
 scanf("%d", &n);

 for(i=1; i<=n; ++i)
   {
    reverse();
    printf("\n");
   }

 printf("\nEnd of the program.\n");
 return 0;
 }

You should try to run the program, with yourself taking the part of the computer. Try it, assuming that one word is entered which has two letters. — quamrana
– quamrana, Commented Apr 17, 2014 at 15:06
Also, use the debugger and run your program step by step. You could compile it with gcc -g -Wall and use the gdb debugger (at least on Linux). Use often the backtrace (or bt) command of gdb — Basile Starynkevitch
– Basile Starynkevitch, Commented Apr 17, 2014 at 16:33
In recursion, you can think of execution flow winding itself up in nested blocks of the recursion call, one level deeper for each call, then when the exit criteria is met forcing execution flow to leave that recursion block, it begins to unwind itself, one nested level after the other, each time (in this case) passing by the printf("%c", c); statement, and accessing c in reverse order of stacked values — ryyker
– ryyker, Commented Apr 17, 2014 at 17:17

ryyker · Accepted Answer · 2014-04-17 16:36:36Z

NOTE Your example is at bottom, first your title question: Explaining needed C recursion

Recursion is a programming technique allowing operations to call themselves.
A simple (but meaningless) example would be:

void call(void);
int main(void)
{
    call();
}

void call(void)
{
    call(); 
}

Note: This would simply go until the stack determines too many calls have stacked up, and crash the program.

A more meaningful example (for illustration) would be to write a palindrome character series (A - Z):

void Palindrome(char a)
{
    char b[2];
    sprintf(b, "%c", a);
    printf(b);
    if((a >= 65)&&(a < 90))
    {
        Palindrome(a+1);
    }
    sprintf(b, "%c", a);
    printf(b);
}

This last example actually does two important things the first example did not do:
1) has a controlled exit criteria if((a >= 65)&&(a <= 90))
2) uses the results of prior calls with subsequent calls.

In your example: The reason the program works is that each time the operation calls itself, it is nesting deeper (one nest for each call) into the section: (this is true for all recursive programs)

  {
    reverse();
  }

Similar in concept to:

{
    //do something
    {
        //do something
        {
            //do something
            //... and so on for as many recursions are necessary to meet exit criteria
        }
    }
}

"...but then how does it print out the reversed word?"
Only after the recursion reaches the programmed limit does execution flow down past the closing } and hit the next section, where it continues to unwind itself, each time accessing, in reverse order of stack, the values of c until each nested level has been unwound:

     }  //after exit criteria is met, execution flow goes from here....
     printf("%c", c); //prints values of c in reverse order.
 } //to here until number of recursions is exhausted.

at that time, if you step through using a debugger, you will see flow going from the upper } to the lower } executing printf() each time.

Thanks a lot mate, your explanation was very clear and concise and I feel as if I understand recursion better now. Thank you for clearing this up for me.

Codor · Accepted Answer · 2014-04-17 15:06:07Z

0

It is indeed a bit difficult to get; the reversal by recursion works by recursively getting more and more characters from the input until some terminal symbol ' ' is entered. The input is stored implicitly on the stack, until it is printed at the termination of each recursive call of reverse.

Note that the characters are only printed to the output, but they are not stored anywhere for later access; they cannot be obtained again as soon as the first call of reverse terminates.

answered Apr 17, 2014 at 15:06

Codor

17.6k9 gold badges32 silver badges59 bronze badges

Collectives™ on Stack Overflow

Explaining needed C recursion

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related