By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
462,143 Members | 722 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 462,143 IT Pros & Developers. It's quick & easy.

Understanding a recursive function call

P: 1
Expand|Select|Wrap|Line Numbers
  1. #include<stdio.h>
  2.  void myfunc(int x)
  3.  {
  4.     if(x>0)
  5.        myfunc(--x);
  6.     printf("%d,",x);
  7.  }
  8.  
  9.  int main()
  10.  {
  11.     myfunc(5);
  12.     return 0;
  13.  }
here i understood still "0" prints..but after that how it will prints 1234?
Jun 3 '10 #1
Share this Question
Share on Google+
9 Replies

Expert 100+
P: 2,418
Your main function calls myfunc once.
myfunc either prints a single number or it doesn't print anything.
Therefore, the output of this program will either be a single number or nothing.

I don't understand the last line of your post.
Are you saying that you observe "0" to be printed?
Are you saying that you expect "1234" to be printed?

Personally, I would expect this program to print "4", and nothing more.

By the way, it is not uncommon for stdout to use buffered I/O. That means you wouldn't see anything printed out until you print a newline. I advise you to either change "%d" to "%d\n" in your printf call or add another printf just before the return statement in main (this new printf would print only a newline character).
Jun 3 '10 #2

P: 13
This is happening bcoz of recurrive calls for function myfunc(). Use a debugger and go step by step you will get the answer
Jun 4 '10 #3

100+
P: 542
Also it is poor technique not to initialize x to 0 or 1 but am unsure what affect this would have in this case as have not run it
Jun 4 '10 #4

Expert 100+
P: 2,418
Please disregard everything I said in my earlier reply (except the part about buffered output). I completely missed the recursion.

The output I would expect from this program is "001234".

You might want to add printf("\n"); immediately before the return statement in main. That will guarantee the output is seen regardless of whether the program is run on a system with buffered or unbuffered output for stdout.
Jun 4 '10 #5

100+
P: 542
"The output I would expect from this program is "001234""
An infinitesimal nitpick... should have been 0,0,1,2,3,4
But I simply can`t see why. Can only see 4,3,2,1
Could someone explain?
Jun 6 '10 #6

Dheeraj Joshi
Expert 100+
P: 1,123
4 3 2 1 is the expected output.

Regards
Dheeraj Joshi
Jun 6 '10 #7

P: 23
The correct output of this program is "0,0,1,2,3,4,".

When using recursive function calls, execution path has two directions: winding and unwinding.

Winding is when your condition (x>0) is true and you call myfunc(--x). Note that no call to printf(...) is reached during the winding process!

Once your condition (x>0) is false, and you stop calling myfunc(--x), the first printf(...) is reached and since x is zero, you're printing "0,".

Now the unwinding begins - each call to myfunc(--x) returns to it's caller, and execution continues right after the recursive call which is your printf(...). At this point the value of x is that which existed in that calling function before the call was made.

Remember this (important!): each recursive call maintains x's value as it was during that particular call. This means that each myfunc() has its own x value which equals the parent's x minus 1.

So.... you now unwind to the parent function: myfunc(--1) and execution continues at the printf(..) which means that "0," is printed again because --1 equals zero. That's "0,0," so far.

Unwind a step back, and you get to myfunc(--2) which prints "1,".
"0,0,1," so far.
Unwind a step back, and you get to myfunc(--3) which prints "2,".
"0,0,1,2," so far.
Unwind a step back, and you get to myfunc(--4) which prints "3,".
"0,0,1,2,3" so far.
Unwind a step back, and you get to myfunc(--5) which prints "4,".
"0,0,1,2,3,4," so far.

Now you've reached the end (or the beginning, if you'd like) of your unwinding.
So the result is "0,0,1,2,3,4,".

If you're not sure how this works, use printf() to see what x is equal to in each iteration:

Expand|Select|Wrap|Line Numbers
  1. #include <iostream>
  2.  
  3. void myfunc(int x)
  4. {
  5.  
  6.     if(x>0)
  7.         {
  8.             printf("we're in myfunc(%d) and winding down...\n",x);
  9.             myfunc(--x);
  10.         }
  11.     else printf("\nx = %d, time to unwind, and call printf()...\n",x);
  12.     printf("%d,",x);
  13. }
  14.  
  15. int main()
  16. {
  17.     myfunc(5);
  18.     return 0;
  19. }
  20.  
Also, check out figure 3 in this tutorial:
http://www.csc.liv.ac.uk/~frans/OldL...recursion.html

I hope I got this right, and that it makes sense.

Peace.
Jun 6 '10 #8

Banfa
Expert Mod 5K+
P: 8,968
That explaination seems correct to me and I concur that the output should be "0,0,1,2,3,4," :D

The only thing to add is that when calling a function recursively it is slightly more normal to call the next iteration with the next increment (or decrement) in the sequence without altering the value the current function is working on so

myfunc(x-1);

Pass an altered value to the next iteration without altering our own value. Alter the program to use this and the output becomes "0,1,2,3,4,5,".
Jun 6 '10 #9

100+
P: 1,059
While you will debug also check your function stack after every time myfunc get called you may get a clear picture(in fact after seeing stack, recursive function became a piece of cake during my graduation)

in stack you may see like this
myfunc(0)
myfunc(1)
myfunc(2)
myfunc(3)
myfunc(4)
myfunc(5)
main()
(i am not sure about proper stack output right now )
it means main function called myfunc with parameter 5, myfunc with parameter 5 called myfunc with parameter 4 and so on

I hope you will understand it after watching stack
Best Regards,
Johny
Jun 7 '10 #10

Post your reply

Sign in to post your reply or Sign up for a free account.