0
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void recursie(int);

int main(int argc, char **argv) {
  recursie(3);
}

void recursie(int a){
  if(a==0){return;}
    recursie(a-1);
    printf("%d",a);
    recursie(a-1);
}

The output is : 1213121. Can someone explain me how i get to this output ?

2
  • Try replacing the "%d" format string with "%d\n" and use a debugger (like gdb); you could also add more printf. But I don't understand what is surprising you. Aug 25, 2012 at 13:45
  • 3
    What did you expect, and why? Aug 25, 2012 at 13:46

4 Answers 4

8
recursie(3)
  -calls recursie(2)
   - calls recursie(1)
     -calls recursie(0) -> void
     -prints 1
     -calls recursie(0) -> void
   -prints 2
   -calls recursie 1
      -calls recursie 0 -> void
      -prints 1
      -calls recursie 0 -> void
  -prints 3
  -calls recursie(2)
   - calls recursie(1)
     -calls recursie(0) -> void
     -prints 1
     -calls recursie(0) -> void
   -prints 2
   -callse recurse 1
      -calls recusie 0 -> void
      -prints 1
      -calls recursie 0 -> void
end
2

This happens because of the order in which recursion occurs vis a vis that of the prinf(). If you work out the order of calls, ignore recursie(0) because it is a no-op (does nothing) and flatten them to a simple list of statements what you get is:

recursie(3-1);
printf("%d", 3);
recursie(3-1);

Which leads to:

recursie(2-1);
printf("%d", 2);
recursie(2-1);
printf(3);
recursie(2-1);
printf("%d", 2);
recursie(2-1);

Which in turn works out as:

printf("%d", 1);
printf("%d", 2);
printf("%d", 1);
printf("%d", 3);
printf("%d", 1);
printf("%d", 2);
printf("%d", 1);
1

The output of calling it on n is the string of n surrounded by two copies of the output of calling it on n-1, except that the output of calling it on 0 is nothing. This means the output of calling it on 1 is "1", so the output of calling it on 2 is "121" ("2" surrounded by copies of "1"), and the output of calling it on 3 is "1213121" ("3" surrounded by two copies of "121").

0

When new concepts like these seem confusing, grab a piece of notebook paper and graph everything out. You'll see that the reason that the number 3 is in the center is that you're running two recursive functions on either side of its printing, leaving an equal padding for 3 to be in the center. The next is that 2 is left in the center of its padding (1's). This is for the same reason that 3 is in the center. 1 is on either sides and there are no 0s because you said if 0, stop.

Was there a specific result you were looking for that wasn't achieved?

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.