Why does the C# compiler not even warn about endless recursion?

Question

A legacy app is in an endless loop at startup; I don't know why/how yet (code obfuscation contest candidate), but regarding the method that's being called over and over (which is called from several other methods), I thought, "I wonder if one of the methods that calls this is also calling another method that also calls it?"

I thought: "Nah, the compiler would be able to figure that out, and not allow it, or at least emit a warning!"

So I created a simple app to prove that would be the case:

public partial class Form1 : Form
{
    public Form1()
    {
        InitializeComponent();
    }

    private void button1_Click(object sender, EventArgs e)
    {
        method1();
    }

    private void button2_Click(object sender, EventArgs e)
    {
        method2();
    }

    private void method1()
    {
        MessageBox.Show("method1 called, which will now call method2");
        method2();
    }

    private void method2()
    {
        MessageBox.Show("method2 called, which will now call method1");
        // Note to self: Write an article entitled, "Copy-and-Paste Considered Harmful"
        method1();
    }
}

...but no! It compiles just fine. Why wouldn't the compiler flag this code as questionable at best? If either button is mashed, you are in never-never land!

Okay, sometimes you may want an endless loop (pacemaker code, etc.), but still I think a warning should be emitted.

Answer 1

1. As you said sometimes people want infinite loops. And the jit-compiler of .net supports tailcall optimization, so you might not even get a stack overflow for endless recursion like you did it.

2. For the general case, predicting whether or not a program is going to terminate at some point or stuck in an infinite loop is impossible in finite time. It's called the halting problem. All a compiler can possibly find are some special cases, where it is easy to decide.

Answer 2

That's not an endless loop, but an endless recursion. And this is much worse, since they can lead to a stack overflow. Endless recursions are not desired in most languages, unless you are programming malware. Endless loops, however, are often intentional. Services typically run in endless loops.

In order to detect this kind of situation, the compiler would have to analyze the code by following the method calls; however the C# compiler limits this process to the immediate code within the current method. Here, uninitialized or unused variables can be tracked and unreachable code can be detected, for instance. There is a tradeoff to make between the compiling speed and the depth of static analysis and optimizations.

Also it is hardly possible to know the real intention of the programmer.

Imagine that you wrote a method that is perfectly legal. Suddenly because you are calling this method from another place, your compiler complains and tells you that your method is no more legal. I can already see the flood of posts on SO like: "My method compiled yesterday. Today it does not compile any more. But I didn't change it".

Answer 3

To put it very simply: it's not the compiler's job to question your coding patterns.

You could very well write a Main method that does nothing but throw an Exception. It's a far easier pattern to detect and a much more stupid thing to do; yet the compiler will happily allow your program to compile, run, crash and burn.

With that being said, since technically an endless loop / recursion is perfectly legal as far as the compiler is concerned, there's no reason why it should complain about it.

Actually, it would be very hard to figure out at compile time that the loop can't ever be broken at runtime. An exception could be thrown, user interaction could happen, a state might change somewhere on a specific thread, on a port you are monitoring, etc... there's way too much possibilities for any code analysis tool out there to establish, without any doubt, that a specific recursing code segment will inevitably cause an overflow at runtime.

I think the right way to prevent these situations is through unit testing organization. The more code paths you are covering in your tests, the less likely you are to ever face such a scenario.