1

I have the following code in c#

class Program
{
    private static int WriteToConsole(int NumWrites)
    {
        int i  =  NumWrites;
        while( i > 0)
        {
            Console.WriteLine("Loop {0}",  i);
            i = WriteToConsole( i – 1);
        }
        return NumWrites – 1;
    }   
    static void Main()
    {   
        WriteToConsole(3);
        Console.ReadKey();
    }
}

With the question "What does the console show after running this?"

The correct answer is 3 2 1 1

But I don't understand where the extra one is coming from in this loop. After the first loop that writes 1 to the console, doesn't returning NumWrites (Which is 1 at this point) minus 1 equal 0, making int i 0 and stop the loop before it can run again with 0? I know I'm missing a step but can really pin down where.

Chris Dunaway
  • 10,974
  • 4
  • 36
  • 48
VRS
  • 11
  • 1
  • Your double quotes aren't double quotes in C# .. At least not for my IDE (VStudios2019) – Jaskier Nov 12 '19 at 17:56
  • 1
    It's due to recursive call you are making inside `WriteToConsole` method. – Akash KC Nov 12 '19 at 18:04
  • 1
    I bet is because the recursive part is in a loop and the loop does not completely unwind until the last recursive frame finishes -->1. Then the loop unwinds backwards because of the function result -1, 0 1 in case 1 >0. – Ross Bush Nov 12 '19 at 18:20
  • Why do you need to reassign i in the loop? Couldn't NumWrites be checked as your exit condition prior to the loop? – Ross Bush Nov 12 '19 at 18:28
  • Sorry if it's a bit weird, I had to re-write it in word, it's from a practice test I couldn't copy and paste from. – VRS Nov 12 '19 at 18:43

2 Answers2

2

I modified your code with a few print statements to help understand where the loop is going here:

private static int WriteToConsole(int NumWrites)
    {
        int i  =  NumWrites;
        Console.WriteLine("i is " + i);
        Console.WriteLine("NumWrites is " + NumWrites);
        while( i > 0)
        {
            Console.WriteLine("Loop {0}",  i);

            Console.WriteLine("Calling WriteToConsole(" + (i-1) + ")" + "\n");
            i = WriteToConsole( i - 1);
            Console.WriteLine("i is now " + i + "\n");
        }

        Console.WriteLine("Returning " + (NumWrites - 1));
        return NumWrites - 1;
    }

This prints the following: 

i is 3
NumWrites is 3
Loop 3
Calling WriteToConsole(2)

i is 2
NumWrites is 2
Loop 2
Calling WriteToConsole(1)

i is 1
NumWrites is 1
Loop 1
Calling WriteToConsole(0)

i is 0
NumWrites is 0
Returning -1
i is now -1

Returning 0
i is now 0

Returning 1
i is now 1

Loop 1
Calling WriteToConsole(0)

i is 0
NumWrites is 0
Returning -1
i is now -1

Returning 2

This shows us what's going on in the last two cases where i is 1 and 0. When WriteToConsole(0) gets called, the while loop is not actually being entered. Instead, NumWrites - 1 gets returned. Then, the recursive 'tree' gets unrolled, because you have hit your edge case of recursion.

Because i is now less than 0, you hit the return NumWrites - 1 statement multiple times, but backwards: first, -1 gets returned. Then, 0 gets returned. Then, 1 gets returned. When 1 gets returned, this sets i to 1, once again. When this happens, Loop 1 prints for the second time.

After the final 2 is returned, your recursive 'tree' has unrolling.

CEH
  • 5,701
  • 2
  • 16
  • 40
  • 1
    Right -- modifying my answer to explain the two cases where `i` is 1 and 0, causing the `Loop 1` to print twice. – CEH Nov 12 '19 at 18:04
  • Beautifully written and very well explained! – Jaskier Nov 12 '19 at 18:23
  • Alright, I see now how the return interacts and brings it into the negatives, and if I'm understanding properly the WriteToConsole is bringing it back to 0 on the following loop, but how does the return of - 1 bring it to positive 1? Is it actually climbing back up or has the code ended at the second 1? – VRS Nov 12 '19 at 18:33
  • So, the return value of -1 is the peak of your recursive loop. You have reached your "edge" case here, which tells the program to stop calling itself. Now, instead of calling itself, you are returning values instead -- because your `while` loop has been getting hit, no values have been returned yet. Notice how in the console output, "returning 1" did not get printed until after the -1 case was called. Returning the values is calling `WriteToConsole` again -- so the 1 that gets returned gets passed back into `WriteToConsole`. – CEH Nov 12 '19 at 18:40
  • So on the loop where it starts calling returns the NumWrites goes from 0 to -1, but what I'm not understanding is why it starts climbing back into the positives, shouldn't it continuously subtract positives and head further into the negatives? Or is it using absolute value, in which case isn't it going to just go back and forth between 0 and -1? Obviously it's not but I can't seem to grip **why** it's going back to 1 and executing that final loop, or even why that is the final loop. I'm just stuck on the -1 - 1 = 0, 0 - 1 = 1 thing. – VRS Nov 12 '19 at 18:50
  • Imagine each method call getting added to a "stack", then removed from the top of the stack when that method call actually gets executed, your `WriteToConsole()` method has stacked with values: 3, 2, 1, 0. Once we hit the 0 case, the base condition is hit (`i > 0`) and the method calls un-stack by executing the call. -- that's how we "move up" from 0 to 1. It's difficult to explain recursion without visual aid to imagine the "stack" of calls -- image in this thread may help: https://stackoverflow.com/questions/19865503/can-recursion-be-named-as-a-simple-function-call/19865640#19865640 – CEH Nov 12 '19 at 19:07
  • I'm not sure I understand, so as the Stack pops, the older variables in the memory are called on by the return call? Wouldn't that also lead to it writing **loop 2** after the second **loop1** before it completes its un stack since it had the variable 3 at the very beginning? – VRS Nov 12 '19 at 19:32
  • 2 is the result of last call item in the stack -- remember, you are returning `NumWrites - 1`, so 2 comes from the initial `3` that was called -- meaning, `NumWrites` is equal to 3 here. Because it is last item in call stack, the program ends after `return NumWrites - 1`. The final `Loop 1` that gets printed comes from the `WriteToConsole(2)` call that gets popped off the stack eventually. The popped method calls against 1 and 0 do not print any `Loop` because 1 and 0 do not meet the condition of the while loop -- they are read in as 0 and -1 due to the `WriteToConsole(i - 1)` call. – CEH Nov 12 '19 at 19:42
  • I think I've got it up to the final parts of the stack. The 0 and 1 are both less than 0 after `NumWrite - 1`. The 2 is the second `loop1.` For the final stack call of 3 with `NumWrite - 1` would make 2, but isn't written to the console since it was at the bottom of the stack and the code is completed. Thank you for all your help and explanations, I think I understand it now. – VRS Nov 12 '19 at 19:58
  • I recommend trying out recursion with a more simple program -- while this one appears simple, it's actually a bit complicated. Something such as a factorial method will help demonstrate the concept of the stack in recursion-- when calculating factorial recursively, you are "stacking" the calls like factorial(5), factorial(4), factorial(3)...then when we hit 1, factorial(1) is just 1. Once we hit that "base" case / condition, we pop the stack off -- factorial(2)...all the way to factorial(5). Each successive call is calculated by using the result of the previous call in the stack. – CEH Nov 12 '19 at 20:49
1

The best way to understand this is to think about what does WriteToConsole function accepts on each iteration and what does it returns:

Inputs: 3  -> 2 -> 1 -> 0
Outputs: -1 -> 0 -> 1 -> 0

Since the condition in a while loop is i > 0 it will execute one extra operation after 1 is returned from the function.

Fabjan
  • 13,506
  • 4
  • 25
  • 52