CODEWITHSUNDEEP
c#
PiousVenom
PiousVenom

Reputation: 6908

How to break out of this loop

I'm working on Project Euler number 5. I've not Googled, as that will typically lead to a SO with the answer. So, this is what I've got:

    private int Euler5(int dividend, int divisor)
    {
        if (divisor < 21)
        {
            // if it equals zero, move to the next divisor
            if (dividend % divisor == 0) 
            {
                divisor++;
                return Euler5(dividend, divisor);
            }
            else
            {
                dividend++;
                return Euler5(dividend, 1); // move to the dividend
            }
        }
        // oh hey, the divisor is above 20, so what's the dividend
        return dividend; 
    }

In my mind, this makes sense. Yet VS2012 is giving me a StackOverFlowException suggesting I make sure I'm not in an infinite loop or using recursion. My question is, why is this an infinite loop? I've a feeling I'm missing something completely silly.

EDIT

Since people seem to keep posting them, I'll reiterate the fact that I didn't use Google for fear of stumbling on the answer. I don't want the answer to the problem. I only wanted to know why I was getting the exception.

Upvotes: 5

Views: 180

Answers (2)

jods
jods

Reputation: 4591

+1 for Jason's answer, which clearly explains the problem.

Now for some solution! I know at least of three ways to remove recursion from an algorithm:

  1. Find a purely iterative algorithm instead (which can be difficult for some problems);
  2. Transform the recursive algorithm into a similar one with a loop and use a Stack<T> (or some kind of list) to store the equivalent of the call stack. This has similar space requirement as the original one, but the heap can grow much bigger than the stack!
  3. A special family of recursive algorithms are tail-recursive. Those can easily mechanically be changed to never overflow the stack. You're lucky, it's your case!

An algorithm is tail-recursive if all its recursive calls are tail-calls, which means they are the last thing done before returning. If it's unclear to you, lookup better examples with Google.

Such algorithms can easily be transformed by adjusting the parameters and using a goto rather than a real call. Look at your example again:

private int Euler5(int dividend, int divisor)
{
    tail_call:
    if (divisor < 21)
    {
        // if it equals zero, move to the next divisor
        if (dividend % divisor == 0) 
        {
            divisor++;
            goto tail_call; // return Eular5(dividend, divisor);
        }
        else
        {
            dividend++;
            // return Eular5(dividend, 1); // move to the dividend
            divisor = 1;
            goto tail_call;
        }
    }
    // oh hey, the divisor is above 20, so what's the dividend
    return dividend; 
}

Oh hey! It's exactly the same function, but with a fixed stack size (there's no call, only jumps). Now some would say: "Ugh... gotos! They are evil! Die goto, die!". I'd say this is one of the few legitimate uses. After all if your compiler was smart enough, it would do the tail-call optimization itself (F# actually does, C# does not, the JIT might do it on x64, not on x86).

But for those people I'd say: look a little better. Because there is a goto at the end of each if/else branch, I can move it outside of the "if" completely. Now I have something like "start: if (X) { Y(); goto start; }" Think about it, it's just a "while(X) Y()" loop. So you just found the iterative version of your function:

private int Euler5(int dividend, int divisor)
{
    while (divisor < 21)
    {
        // if it equals zero, move to the next divisor
        if (dividend % divisor == 0) 
        {
            divisor++;
        }
        else
        {
            dividend++;
            divisor = 1;
        }
    }
    // oh hey, the divisor is above 20, so what's the dividend
    return dividend; 
}

Nice!

Upvotes: 1

jason
jason

Reputation: 241591

Of course this kind of logic is going to blow the stack. Think about this, if you were to implement this logic to solve the problem of finding the smallest number evenly divisible by 1--10, you'd be at least 2520 calls deep in the stack, per the problem statement:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

For 1--20, the answer is obviously much larger and it's not surprising at all that you're blowing the stack. You should find a non-recursive solution.

My question is, why is this an infinite loop?

It's not. The stack is limited in size. You're making too many recursive calls and eventually breaching the maximum stack size.

I've a feeling I'm missing something completely silly.

You came to the right place.

Upvotes: 10

Related Questions