0

As a beginner, I am pretty confused about the manner in which the following C# recursion can run.

class program
{
    public void Count(int inVal)
    {
        if(inVal == 0)
           return;
        Count(inVal - 1);
        Console.WriteLine("{0}",inVal);
    }

    static void Main()
    {
        Program pr = new program;
        pr.Count(3);
    }
}

From my perspectives, the 'program' should stop when 'intVal' reaches 0 because the flow cannot pass through 'if(intVal == 0) return;'. How can it print out '1 2 3' sequentially? I would appreciate it if anyone knows the principles among them.

Fruchtzwerg
  • 10,999
  • 12
  • 40
  • 49
wang ted
  • 35
  • 4
  • 5
    `How can it print out '1 2 3' sequentially` - thats [exactly what your code does](http://rextester.com/FYGG86078) – Jamiec Jun 26 '17 at 16:04
  • It prints when it's *returning* from the recursion. What you need to do is write out in pencil on a piece of paper, each step that happens, in order. Absolutely everything that happens: 1. Call Count with `inVal=3`. 2. Check `inVal ` against zero. 3. Call Count with `inVal=2` -- and so on. Do that and you will see what it is doing. Don't try to understand code all at once. Break it down into small pieces. – 15ee8f99-57ff-4f92-890c-b56153 Jun 26 '17 at 16:05
  • The return will be returning to the previous iteration of the method Count() – Sean T Jun 26 '17 at 16:05
  • Just switch the Count() line and the WriteLine(). You are seeing one less because you decremented before writing. The other choice would be to return when inVal is less than zero. Both methods are correct, it just depends on your implementation. – jdweng Jun 26 '17 at 16:08
  • 1
    For educational purposes, try replacing the calls to Count by the actual method's content, and you will get it. – Kilazur Jun 26 '17 at 16:09
  • 2
    I think the real issue OP might be having is thinking that `return` will somehow skip over the rest of the execution. If you want to `break` from a loop, I don't think recursion would be the approach – maccettura Jun 26 '17 at 16:36

3 Answers3

3

The way you have it structured now, you are recursively calling Count() before you print out what your value is at that level, so your program flow looks like this:

Main
  --> Count(3)
    --> Count(2)
      --> Count(1)
        --> Count(0) //here, the program returns because of your if
      --> //prints 1
    --> //prints 2
  --> //prints 3

Hopefully that shows the way your program is running currently, and helps process why it's sequentially printing out values. The issue is that code after a recursive call only executes after that recursive call is complete - for Count(3), this means Count(2), Count(1), and Count(0) all happen before the print statement in Count(3).

josephmbustamante
  • 352
  • 6
  • 19
  • Related to this answer: https://stackoverflow.com/questions/25676961/understanding-how-recursive-functions-work – Dewick47 Jun 26 '17 at 16:09
2

I remember being confused about recursion as well so let's see if I can explain what happens.

  1. You call Count with 3
    1. Count checks that 3 == 0, and gets false, hence it does not return
    2. It then calls itself with 2 (3-1)
      1. Count checks that 2 == 0, and gets false
      2. It then calls itself with 1 (2-1)
        1. Count checks that 1 == 0, and gets false
        2. It then calls itself with 0 (1-1)
          1. Count checks that 0 == 0, and gets true, hence it returns
        3. Count now prints 1
        4. We now exit the bottom of the method, returning back up to the previous call stack
      3. Count now prints 2
      4. We now exit the bottom of the method, returning back up to the previous call stack
    3. Count now prints 3
    4. We now exit the bottom of the method, returning back up to the previous call stack
  2. You're back in Main
Lasse V. Karlsen
  • 380,855
  • 102
  • 628
  • 825
  • I wonder where the 'return' returns to. – wang ted Jun 27 '17 at 03:49
  • It always returns back to the place your method was called from, and then continues executing with the statement following your method call. – Lasse V. Karlsen Jun 27 '17 at 06:49
  • Consider it like this. You're folding laundry. The phone rings. You leave the laundry, go pick up the phone, you finish with the phone and put it back down, you return to your laundry and continue where you left off. A method call is nothing different. You call a method, execution continues in that other method until it returns, then you go back and continue with whatever your program were doing when it called the method, continuing execution after the method call. – Lasse V. Karlsen Jun 27 '17 at 06:51
  • Aha, very specific and understandable, got it. Thank u! – wang ted Jun 27 '17 at 08:40
1

Follow the stack trace as the code runs through. Note that it doesn't print until after the recursive Count() method is called.

The stack is hard to visualize without a graphic, but:

...Count(3)
  ... Count(2)
     ... Count(1)
       ... Count(0)
     ... ResumeCount(1)
  ... ResumeCount(2)
... ResumeCount(3)

Each time you call Count again, the current method's processing stops until the subsequent call returns.

The process flow looks something like this:

  1. Receive call to Count from main program with value of 3
  2. Check if value is 0
  3. Run Count again, pass it value of 2 (we've now added another Count() method to the stack... the original one is waiting for this to return)
  4. Check if value is 0
  5. Run Count again, pass it a value of 1
  6. Check if value is 0
  7. Run Count() again, pass it value of 0
  8. Check if value is 0
  9. Value **is* 0, return from this one
  10. Falls back into prior instance of the method (where #7 left off)
  11. Print 1
  12. Returns and falls back to prior instance (where #5 left off)
  13. Print 2
  14. Returns and falls back or prior (original) instance (where #3 left off)
  15. Print 3

Walk through in a debugger and you'll see...

If you move the ConsoleWriteLine call before the Count call, you'd have 3, 2, 1 instead of 1, 2, 3

jleach
  • 7,410
  • 3
  • 33
  • 60