Why does this recursive function generate this output?

Question

I am trying to understand the output of the program printed below. When I look at it, I see that when printnum() is called with an argument of 1, "1" will be printed and then since 1<7, the function will call itself. This process will continue until "6" is printed and then printnum(7) is called. So, now "7" is printed and the if condition is not satisfied, so that code is skipped and we move to the second printf("%d", x) function where "7" is printed out again. There is nothing after the second printf("%d", x), so why doesn't everything end there? What makes the program keep going to print the numbers again in descending order?

#include <stdio.h>

int printnum ( int x )
{
  printf("%d", x);

  if ( x < 7 )         
  {
      printnum ( x + 1 );    
  }
  printf("%d",x);         
}

int main()
{
printnum(1);
}

Output:

12345677654321

First of all, I doubt that printnum(8) is ever called; it's called with x + 1 only if x < 7 holds, so the largest value it's called with is 7. Furthermore, I believe the output you wrote lacks a 3. — Frerich Raabe
– Frerich Raabe, Commented Dec 22, 2011 at 12:51

Sebastian Paaske Tørholm · Accepted Answer · 2011-12-22 12:55:42Z

5

printnum(8) is never called, because it isn't true that 7 < 7.

The reason that you get the numbers printed in descending order once x = 7 is reached is, that each recursive call ends, leaving the previous call to continue.

Consider what it does for x = 1:

Print 1
Call recursively with x = 2
Print 1

If we expand this one level more:

Print 1
- Print 2
- Call recursively with x = 3
- Print 2
Print 1

And one more:

Print 1
- Print 2
  - Print 3
  - Call recursively with x = 4
  - Print 3
- Print 2
Print 1

If you continue this expansion, you can see you get numbers in ascending order before the recursive call, and in descending order after the recursive call.

edited Dec 22, 2011 at 12:55

answered Dec 22, 2011 at 12:49

Sebastian Paaske Tørholm

51.3k11 gold badges103 silver badges123 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

bqui56 Over a year ago

Ah yeh, sorry forgot to update my text. I think you get my question though?

Sebastian Paaske Tørholm Over a year ago

@stanz77: I expanded upon my answer. :)

Nate · Accepted Answer · 2011-12-22 12:50:21Z

4

This happens because the second printf is called after your recursion exits at each level.

As your final recursive call printfs and ends, control transitions to the function that called it - the second-to-last recursive call. This call then exits the scope of the if statement, and calls printf, and then ends - upon which control transitions to the function that called it - the third-to-last recursive call. Repeat until you are inside the call to printnum(1), whose return takes you back to main.

answered Dec 22, 2011 at 12:50

Nate

12.9k5 gold badges48 silver badges62 bronze badges

Comments

Simone-Cu · Accepted Answer · 2011-12-22 12:56:14Z

1

It's recursion. When you enter the function you call printf, then you enter another level in the recursion, then you enter the printnum, so you call the printf with x+1 and so on. When you arrive at stop condition (x==7), the function goes till the second printf (so 7 will be displayed again).
The function printnum terminates, so the program returns at the level above, then printnum at level 6 can printf again, terminate and return and so on.

answered Dec 22, 2011 at 12:56

Simone-Cu

1,1298 silver badges22 bronze badges

Comments

Sangeeth Saravanaraj · Accepted Answer · 2011-12-22 13:10:50Z

Comments in-line!

int printnum ( int x )              x = 1                   x = 2                   x=6                     x=7 
{   

  printf("%d", x);                  prints 1                prints 2                prints 6                prints 7

  if ( x < 7 )                      Yes                     Yes                     Yes                     No  
      printnum ( x + 1 );           calls printnum(2)       calls printnum(3) ....  calls printnum(7)       N/A 

  printf("%d",x);                   print 2 and return to   print 6 and return      prints 7 and returns to the 
                                    the caller which is     the previous caller     to the previous         previous caller which is  
                                    main()                  which is printnum(1)    caller which is         printnum(x=6)
                                                                                    printnum(5)
}

Please check the following to print in ascending and descending order passing the starting value and the limit.. (please note that the error checking is not done!)

#include <stdio.h>

int printnum_123(int x, int limit)
{
    printf("%d ", x);
    if (x<limit)     
        printnum_123(x+1, limit);
    return;
}

int printnum_321(int x, int limit)
{
    if (x<limit)
        printnum_321(x+1, limit);
    printf("%d ", x);
    return;
}

int main(void)
{
    printnum_123(1, 10); printf("\n");
    printnum_321(1, 10); printf("\n");
    return 0;
}

$ ./a.out
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
$

Collectives™ on Stack Overflow

Why does this recursive function generate this output?

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related