0

This is a recursive program. But I don't understand the sequence of events which take place during this program

#include<stdio.h> count(int); main() { int x=5; count(x); } count(int y) { if(y>0) { count(--y); printf("%d ",y); } }

the output is:

4 3 2 1 0 ...

But I don't get what happens when the first time count(5) is called and when count(4) is called. Does the control immediately go to the start of the function? Or first it prints the value of y and then again goes to the start of the function count()?

Improve this question
7
  • 2
    Try to use a debugger (on Linux that means gdb after having compiled with gcc -Wall -g), run the program step by step or at least with a breakpoint in count Commented Aug 2, 2012 at 9:15
  • are you asking that how the program is executing? Step-by-step?? Commented Aug 2, 2012 at 9:21
  • 3
    @chris the program doesn't use void main; it uses assumed return int, which is pre-ISO (K&R) C. Commented Aug 2, 2012 at 9:22
  • yes i want learn the control sequences Commented Aug 2, 2012 at 9:22
  • @ecatmur, It was void when I posted. Commented Aug 2, 2012 at 9:27

5 Answers 5

Reset to default
5

It is like a stack of dishes.

 1 2 3 4 5 count(0) count(1) count(1) count(2) count(2) count(2) count(3) count(3) count(3) count(3) main main main main main count(0) prints nothing

go to step 4

count(1) prints 1

go to step 3

count(2) prints 2 ...

So to get the output of 4 3 2 1 you need to swap around the count(--y) and the printf("%d",y) lines.

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

5 Comments

if i swap the lines i will get 5 also
If you swap the lines, printf will be called before --y. So y will still have the value of 5 when it is printed.
i just want to know when the function count(--y) is called ...does the control passes to the start of the function or it prints the vale of y ??
@AmolSingh it will go to the start of the function
@AmolSingh When the function is called, the code in the function is executed ... why or how could you expect anything else?
2

you can easily step through the code to see what happened there, slightly edited code used :

#include<stdio.h> void count(int); int main() { int x=5; count(x); } void count(int y) { if(y>0) { count(--y); printf("%d ",y); } }

now see what happens during the execution. see the gdb session :

(gdb) b count Breakpoint 2 at 0x4004ea: file rc.c, line 10. (gdb) c Continuing. Breakpoint 2, count (y=5) at rc.c:10 (gdb) c Continuing. Breakpoint 2, count (y=4) at rc.c:10 (gdb) c Continuing. Breakpoint 2, count (y=3) at rc.c:10 (gdb) c Continuing. Breakpoint 2, count (y=2) at rc.c:10 (gdb) c Continuing. Breakpoint 2, count (y=1) at rc.c:10 (gdb) c Continuing. Breakpoint 2, count (y=0) at rc.c:10 (gdb) bt #0 count (y=0) at rc.c:10 #1 0x00000000004004fe in count (y=0) at rc.c:12 #2 0x00000000004004fe in count (y=1) at rc.c:12 #3 0x00000000004004fe in count (y=2) at rc.c:12 #4 0x00000000004004fe in count (y=3) at rc.c:12 #5 0x00000000004004fe in count (y=4) at rc.c:12 #6 0x00000000004004dd in main () at rc.c:6 (gdb)

The back trace speaks the whole history. See every call to count is "stacked". But none returned. And nothing printed yet.

Now see how they returned one by one :

(gdb) n count (y=0) at rc.c:13 /* count(y = 0) returned first , it will not cause any printing*/ (gdb) n (gdb) n count (y=1) at rc.c:13 /* count(y = 1) returned second, this will cause printing 0 */ (gdb) n (gdb) n count (y=2) at rc.c:13 /* subsequent returns will cause printing of 1,2,3 etc */ (gdb) n (gdb) n count (y=3) at rc.c:13 (gdb) n (gdb) n count (y=4) at rc.c:13 (gdb) c Continuing. 0 1 2 3 4
Improve this answer

3 Comments

suppose i have a printf("wdf"); statement after count(--y). then what happens ?
you will get a repeated print of "wdf".
when count(y = 0) will return to the place where it get called. It called by count(y = 1). So it will be returned to the instruction after the calling sequence, and will execute whatever there. In this case its a print statement.
0

Well it's like an arithmetic progression. That begin with N > 0 and at each time substract one until reach 0. more on recursion here (use factorial example, and you will understand): http://en.wikipedia.org/wiki/Recursion

Hope this help.

Regards.

Improve this answer

Comments

0 
void count(int y) { if(y>0) { printf("%d ",--y); count(y); } }

prints y-1, y-2, ... 0.

If y <= 0, then there is nothing to do. If y > 0, it decrements y prints the decremented y and then calls count with the decremented value of y to print the remaining values.

Another example, this:

void count(int y) { if(y>0) { printf("%d ",--y); count(y); printf("amol"); } }

prints y-1, y-2, ... 0 amol...amol (y times).

It does so by printing y-1, then it recursively calls count(y-1) to print y-2, ..0, amol (y-1 times), then it prints the remaining "amol".

Improve this answer

5 Comments

suppose after count(y) we have printf("amol") then how will be the output and why
@AmolSingh - what do you think?
@AmolSingh - no, compile and run the program, then try to understand it.
I fail to see how this is an answer to the question.
u are right the output is 4 3 2 1 0 amolamolamolamol but how the statement printf("amol") is exucuting ..?
0

A program can be transformed by replacing things with their equivalents: variables with their values, function calls with the code of the function, conditionals on constants with selected code. e.g.,

main() { int x=5; count(x); }

-->

main() { count(5); }

-->

main() { if(5>0) { count(4); printf("%d ",4); } }

-->

main() { count(4); printf("%d ",4); }

-->

main() { if(4>0) { count(3); printf("%d ",3); } printf("%d ",4); }

--> 

main() { count(3); printf("%d ",3); printf("%d ",4); }

--> ... -->

main() { count(0); printf("%d ",0); printf("%d ",1); printf("%d ",2); printf("%d ",3); printf("%d ",4); }

-->

main() { if(0>0) { count(-1); printf("%d ",-1); } printf("%d ",0); printf("%d ",1); printf("%d ",2); printf("%d ",3); printf("%d ",4); }

-->

main() { printf("%d ",0); printf("%d ",1); printf("%d ",2); printf("%d ",3); printf("%d ",4); }
Improve this answer

2 Comments

that was nice but what if the printf is after the if block?
@AmolSingh Please stop trolling SO.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.