Don't understand output from this recursion code

[lordango]

class Program
{
public void test(int i) {
if (i > 0)
{
test(--i);
}
Console.WriteLi ne(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.WriteLi ne(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?

[IanWright]

class Program
{
public void test(int i) {
if (i > 0)
{
test(--i);
}
Console.WriteLi ne(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.WriteLi ne(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.WriteLi ne() isn't within the if block so will print every time. This means you're program is doing the following:

Test(5)
  i = 4
    Test(4)
      i = 3
        Test(3)
          i = 2
            Test(2)
            i = 1
              Test(1)
              i = 0
                Test(0)
                   we stop here, as i is no longer greater than 0. Now start printing
                   print 0 (then return to calling method Test(1))
              print 0
           print 1
         print 2
      print 3
   print 4
print 5

A better layout, is if you write down in a table:

i --i Console.WriteLi ne(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

[lordango]

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.Diagnost ics.Debug.Print ("x = {0}", x);
if (x <= 1)
{
return 1;
}
return Fibonacci(x - 1) + Fibonacci(x - 2);
}

static void Main()
{
System.Diagnost ics.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?

[IanWright]

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.Diagnost ics.Debug.Print ("x = {0}", x);
if (x <= 1)
{
return 1;
}
return Fibonacci(x - 1) + Fibonacci(x - 2);
}

static void Main()
{
System.Diagnost ics.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

[lordango]

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?

[IanWright]

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...

[lordango]

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.

[IanWright]

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.