473,324 Members | 2,178 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,324 software developers and data experts.

Understanding a recursive function call

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
9 3217
donbock
2,426 Expert 2GB
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
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
whodgson
542 512MB
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
donbock
2,426 Expert 2GB
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
whodgson
542 512MB
"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
1,123 Expert 1GB
4 3 2 1 is the expected output.

Regards
Dheeraj Joshi
Jun 6 '10 #7
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
9,065 Expert Mod 8TB
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
johny10151981
1,059 1GB
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

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

Similar topics

2
by: | last post by:
OK: Purpose: Using user's input and 3 recursive functions, construct an hour glass figure. Main can only have user input, loops and function calls. Recursive function 1 takes input and displays...
4
by: Nicolas Vigier | last post by:
Hello, I have in my python script a function that look like this : def my_function(arg1, arg2, opt1=0, opt2=1, opt3=42): if type(arg1) is ListType: for a in arg1: my_function(a, arg2,...
4
by: Victor | last post by:
Hello, I've got a situation in which the number of (valid) recursive calls I make will cause stack overflow. I can use getrlimit (and setrlimit) to test (and set) my current stack size. ...
9
by: Bill Borg | last post by:
Hello, I call a function recursively to find an item that exists *anywhere* down the chain. Let's say I find it five layers deep. Now I've got what I need and want to break out of that whole...
11
by: randomtalk | last post by:
hi, i have the following recursive function (simplified to demonstrate the problem): >>> def reTest(bool): .... result = .... if not bool: .... reTest(True) .... else: .... print...
1
by: George2 | last post by:
Hello everyone, Such code segment is used to check whether function call or exception- handling mechanism runs out of memory first (written by Bjarne), void perverted() { try{
9
by: pereges | last post by:
Hello I need some ideas for designing a recursive function for my ray tracing program. The idea behind ray tracing is to follow the electromagnetic rays from the source, as they hit the...
3
by: Davy | last post by:
Hi all, Sometimes I need to pass same parameter in recursive function. From my point of view, the style is redundant, and I don't what to use some global style like self.A, self.B, Is there any...
2
by: neovantage | last post by:
Hi Geeks, I am using adodb for accessing my records from MYSQL Database. I define an object of adodb "$db" which is used for executing queries in my configuration file which is accessible in each...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.