473,320 Members | 1,724 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,320 software developers and data experts.

Don't understand output from this recursion code

class Program
{
public void test(int i) {
if (i > 0)
{
test(--i);
}
Console.WriteLine(i);
}

static void Main(string[] args)
{
Program p = new Program();
p.test(5);
Console.ReadKey();
}
}

The output is 0 0 1 2 3 4

I dont quite understand.
I thought that the Console.WriteLine(i); wont execute until i <= 0

and why is that the 0 comes first?

Correct me if im wrong im just new to programming.
Is it because that when a function is called is uses the stack?
so the while the condition is true it keeps calling its self and the first output was actually 4 (because of the pre --yy) but the instruction was on the lowest part of the stack thats why it came out last.

4 3 2 1 0 0 then pops out like 0 0 1 2 3 4

Is that how stack work?

is there a threading happening here?
Jul 29 '08 #1
7 1244
IanWright
179 100+
class Program
{
public void test(int i) {
if (i > 0)
{
test(--i);
}
Console.WriteLine(i);
}

static void Main(string[] args)
{
Program p = new Program();
p.test(5);
Console.ReadKey();
}
}

The output is 0 0 1 2 3 4

I dont quite understand.
I thought that the Console.WriteLine(i); wont execute until i <= 0

and why is that the 0 comes first?

Correct me if im wrong im just new to programming.
Is it because that when a function is called is uses the stack?
so the while the condition is true it keeps calling its self and the first output was actually 4 (because of the pre --yy) but the instruction was on the lowest part of the stack thats why it came out last.

4 3 2 1 0 0 then pops out like 0 0 1 2 3 4

Is that how stack work?

is there a threading happening here?
No, it isn't to do with stacks, its just how you're program is laid out... Write out the flow of the program and think about what it is doing.

--i decreases the value of i before it executes that line... so when you call Test(5), it decreases i and calls test again.. Test(4).

Your Console.WriteLine() isn't within the if block so will print every time. This means you're program is doing the following:

Expand|Select|Wrap|Line Numbers
  1. Test(5)
  2.   i = 4
  3.     Test(4)
  4.       i = 3
  5.         Test(3)
  6.           i = 2
  7.             Test(2)
  8.             i = 1
  9.               Test(1)
  10.               i = 0
  11.                 Test(0)
  12.                    we stop here, as i is no longer greater than 0. Now start printing
  13.                    print 0 (then return to calling method Test(1))
  14.               print 0
  15.            print 1
  16.          print 2
  17.       print 3
  18.    print 4
  19. print 5 
  20.  
A better layout, is if you write down in a table:

i --i Console.WriteLine(i)
5 4 4
4 3 3
3 2 2
2 1 1
1 0 0
0 - 0

then figure out the values each time Test() gets called, then work back up the table to figure out the output...

Hope that helps
Jul 29 '08 #2
Im just new to programming and your reply really helped.
So its just how the program flows.
i tried to look at other recursion samples and i seemed to have gotten lost.

class Program
{
static int Fibonacci(int x)
{
System.Diagnostics.Debug.Print ("x = {0}", x);
if (x <= 1)
{
return 1;
}
return Fibonacci(x - 1) + Fibonacci(x - 2);
}

static void Main()
{
System.Diagnostics.Debug.Print("Fibonacci no. = {0}", Fibonacci(5));
Console.ReadKey();
}
}
***************************************
X=5

Fibonacci(5)
Print 5
Fibonacci(4)
Print 4
Fibonacci(3)
Print 3
Fibonacci(2)
Print 2
Fibonacci(1)
Print 1
--- after this is dont follow anymore :(

does the Fibonacci(x - 2) gets called next?
Jul 30 '08 #3
IanWright
179 100+
Im just new to programming and your reply really helped.
So its just how the program flows.
i tried to look at other recursion samples and i seemed to have gotten lost.

class Program
{
static int Fibonacci(int x)
{
System.Diagnostics.Debug.Print ("x = {0}", x);
if (x <= 1)
{
return 1;
}
return Fibonacci(x - 1) + Fibonacci(x - 2);
}

static void Main()
{
System.Diagnostics.Debug.Print("Fibonacci no. = {0}", Fibonacci(5));
Console.ReadKey();
}
}
***************************************
X=5

Fibonacci(5)
Print 5
Fibonacci(4)
Print 4
Fibonacci(3)
Print 3
Fibonacci(2)
Print 2
Fibonacci(1)
Print 1
--- after this is dont follow anymore :(

does the Fibonacci(x - 2) gets called next?
It's a little more tricky because you have those additions in there. One thing I'd suggest, create a C# application and run it, you can then step through, add watches on variables and find out exactly what its doing.

You're flow is correct so far. You've drilled down recursively into that first Fibonacci(x-1) call, and returned 1. The Fibonacci(x-2) does indeed get called next...

2-2 = 0, so we print 0, and then return 1 based on the logic in the method. Then we add those values for the return

1+1 = 2, so we return 2.

Now we are back to the point where we did Fibonacci(3), so we now need to drill down into the Fibonacci(x-2) for this method aswell...

In doing so, we have called Fibonacci(1) again, so we print 1 and then have then return again... Obviously when we return back up to say our Fibonacci(4) call when we go into Fibonacci(x-2) we're then going to have to drill down into both Fibonacci(x-1) and Fibonacci(x-2) calls again for that function.

Gets quite complicated, I might have even got it wrong as I just did that from looking at it. Create a C# application and try running it, use F11 to step into functions and see what's going on. That's the easiest way with recursion...

Ian
Jul 30 '08 #4
Heres the debug output:

5
4
3
2
1
0
1
2
1
0
3
2
1
0
1
Fibonacci no. = 8

Im so sorry but i just cant see where did the 8 came from?
Jul 30 '08 #5
IanWright
179 100+
It's a little more tricky because you have those additions in there. One thing I'd suggest, create a C# application and run it, you can then step through, add watches on variables and find out exactly what its doing.

You're flow is correct so far. You've drilled down recursively into that first Fibonacci(x-1) call, and returned 1. The Fibonacci(x-2) does indeed get called next...

2-2 = 0, so we print 0, and then return 1 based on the logic in the method. Then we add those values for the return

1+1 = 2, so we return 2.

Now we are back to the point where we did Fibonacci(3), so we now need to drill down into the Fibonacci(x-2) for this method aswell...

In doing so, we have called Fibonacci(1) again, so we print 1 and then have then return again... Obviously when we return back up to say our Fibonacci(4) call when we go into Fibonacci(x-2) we're then going to have to drill down into both Fibonacci(x-1) and Fibonacci(x-2) calls again for that function.

Gets quite complicated, I might have even got it wrong as I just did that from looking at it. Create a C# application and try running it, use F11 to step into functions and see what's going on. That's the easiest way with recursion...

Ian
The 8 is because the Fibonacci(x-1) and Fibonacci(x-2) results add together to give 8... so Fibonacci(4) + Fibonacci(3) = 8...
Jul 30 '08 #6
That would be
(1+2) + (3+2)

is that right?

because i tried to interchange :
Fibonacci(x - 1) + Fibonacci(x - 2)
with
Fibonacci(x - 2) + Fibonacci(x - 1)

and looked at the output.

I figured that the program produces 30 values, (15 values for (x-1) and 15 values for(x-2)) is this correct?

Then it adds the return value f(n-1) + f(n-2) and thats why it returned 8.

its getting clearer now, im still kinda confused about the loop though.
anyway thank you for the post. it really helped.
Jul 30 '08 #7
IanWright
179 100+
I think that's probably right, I think honestly you should look at a simpler recursion example as this is actually quite difficult to follow.

Look at the procedure for calculating the square root of a number manually through recursion, that is quite a simple example, or alternatively try coming up with a recursive binary search.
Jul 30 '08 #8

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

Similar topics

1
by: Tim Mohler | last post by:
All - I have a script that provides a web page interface to various system utilities. Once the user has selected the utility and input various parameters, it calls itself with a different method...
12
by: da Vinci | last post by:
Greetings. I want to get everyone's opinion on the use of recursion. We covered it in class tonight and I want a good solid answer from people in the "know" on how well recursion is accepted...
12
by: Paul | last post by:
Hi, Global operator new and delete are overloaded and I am using stl map to store pointers, but this code crashes, can some one shed some light??? Compiler: MS VC++ 6.0 STL: Shipped with...
2
by: silly | last post by:
/*Thanks again to thos who helped with my 'more hand written integer pow() functions (LONG POST)' query. I needed to write a function to write out integers and after looking at some stuff on...
2
by: Brian Simmons | last post by:
Hi, Long story short: I've got a website built, and we moved it over to the production server, which is an SSL-required (https://...) server. A third party component that I'm using makes use of...
10
by: Lamefif | last post by:
can anyone explain the output of this function. im having trouble comprehending it void ret_str(char* s) { if(*s != '\0') //{ cout<<*(s) ; ret_str(s+1); //cout<<*(s) ;
6
by: =?Utf-8?B?c2VlbWE=?= | last post by:
1) What will the value of txt be after executing MyFunction? public void Main() { string txt = MyFunction( “12345” ); } public string MyFunction( string str ) { if( str.Length == 1 )
3
by: a | last post by:
After several days struggling, I'm still unable to generate a string automatically *ONE by ONE*. I don't want to create a long array memorizing all the output strings and then traverse this array...
9
by: reachmsn | last post by:
Hi, At the url http://www.python.org/doc/essays/graphs.html there is some code by Guido Van Rossum for computing paths through a graph - I have pasted it below for reference - Let's write a...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, youll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
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: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
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: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
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
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
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.