Runtime exception, recursion too deep

Question

I converted the pseudo-code here into C#, and have it recursively repeat 10,000 times. But I get a C# runtime error, StackOverflow Exception after 9217 times. How can I prevent this?

EDIT If it helps anybody, here's the code:

    private double CalculatePi(int maxRecursion)
    {
        return 2 * CalculatePi(maxRecursion, 1);
    }

    private double CalculatePi(int maxRecursion, int i)
    {
        if (i >= maxRecursion)
            return 1;
        return 1 + i / (2.0 * i + 1) * CalculatePi(maxRecursion, i + 1);
    }

    double pi = CalculatePi(10000); // 10,000 recursions

EDIT2 So everybody seems to agree that i need to convert this to iterative... can anybody give some code? I can't seem to write any iterative code that works...

EDIT Thanks to Paul Rieck for this answer, which I tested, and it works:

    private static double CalculatePi(int maxRecursion)
    {
        double result = 1;
        for (int i = maxRecursion; i >= 1; i-- )
        {
            result = 1 + i / (2.0 * i + 1) * result;
        }
        return result * 2;
    }

Answer 1

So everybody seems to agree that i need to convert this to iterative... can anybody give some code? I can't seem to write any iterative code that works...

Are you asking for a fish, or asking to be taught how to catch fish? If the point of this exercise is to learn how to convert recursive code to iterative code then you're not well served by just getting the answer.

To convert recursive code to iterative code there are lots of possible ways to do it. The easiest way in this case is to simply work out the pattern. What does the code do? It computes:

(1 + 1 / (2.0 * 1 + 1)) * 
(1 + 2 / (2.0 * 2 + 1)) * 
(1 + 3 / (2.0 * 3 + 1)) * 
(1 + 4 / (2.0 * 4 + 1)) * 
(1 + 5 / (2.0 * 5 + 1)) * 
(1 + 6 / (2.0 * 6 + 1)) * 
(1 + 7 / (2.0 * 7 + 1)) * 
...
(1 + 9999/ (2.0 * 9999+ 1)) *
1

Now can you write a loop that computes that? Sure.

double product = 1.0;
for (int i = 9999; i >= 0; --i)
    product *= (1 + i / (2.0 * i + 1));

That's the easiest way to do it. But there are lots of ways to solve this problem.

You could use an aggregator. Consider the "total" operation; that's an example of an aggregator. You have a sequence of things and you keep a running total of them, accumulating the result in an accumulator. The standard query operators have an aggregation operation supplied for you:

double seed = 1.0;
Enumerable.Range(0, 10000).Aggregate(seed, 
    (product, i) => product * (1 + i / (2.0 * i + 1))
    

Or, you could keep your algorithm recursive but eliminate the stack overflow by:

• building your own stack structure on the heap
• defining a virtual machine, writing your program in the virtual machine language, and then implementing the virtual machine to keep its stack on the heap.
• rewriting your program in Continuation Passing Style; every step along the way then returns a continuation to the caller, which invokes the next continuation; the stack never gets deep

Explaining those techniques takes too long for one answer. I have a six-part blog series on how to use those techniques to turn recursive programs into programs that don't consume much stack; start reading it here:

Link

Answer 2

The "c# compiler" will compile this fine. At runtime, however, you may end up with a StackOverflow exception (on my machine, 10,000 works fine, but dies later).

This is not an "infinite recursion exception" - stack overflow is exactly what it says; calling a method means putting information on the stack and removing it when the call returns. You have 10,000 calls and none have returned, so the stack is full and the exception is thrown.

You can fix this fairly easily in this particular case by removing the recursion and running iteratively. In the general case, there are ways to remove recursion via iteration, tail-recursion optimization, and continuation passing.

Here's a quick direct translation to an iterative style:

private static double CalculatePi(int maxRecursion)
        {
            double result = 1;
            for (int i = maxRecursion -1; i >= 1; i-- )
            {
                result = 1 + i / (2.0 * i + 1) * result;
            }
            return result * 2;
        }

Answer 3

Don't use recursion. This is a good sample case of when you should not recurse, as you will cause a call stack overflow.

You can probably convert that to non-recursive easily.

Answer 4

The recursive call is not tail-recursive, and even if it were, it wouldn't help since the C# compiler does not currently optimize tail-recursive calls. EDIT: As pointed out by Eric Lippert and Gabe, the CLR could choose to generate tail calls even when explicit tail-call instructions are not in the emitted IL.

1. The best way would be to turn this recursive solution into an iterative one.
2. Since it almost completes, a quick hack might be to increase the stack-size of the thread on which this method runs.

Please don't do this. For fun only:

static void Main()
{
    Console.WriteLine(SafeCalculatePi(10000));
}

// Calculates PI on a separate thread with enough stack-space 
// to complete the computation
public static double SafeCalculatePi(int maxRecursion)
{
    // We 'know' that you can reach a depth of 9217 for a 1MB stack.
    // This lets us calculate the required stack-size, with a safety factor
    double requiredStackSize = (maxRecursion / 9217D) * 1.5 * 1024 * 1024 ; 

    double pi = 0;
    ThreadStart ts = delegate { pi = CalculatePi(maxRecursion); };
    Thread t = new Thread(ts, (int)requiredStackSize);
    t.Start();
    t.Join();
    return pi;
}

Answer 5

You cannot prevent it, the function calls itself too many times; there's a limit on how deep the call stack can get, and your function reaches it.

Answer 6

To glom onto what everyone else is saying here-- this is a Stack Overflow (woot! a Stack Overflow question question on StackOverflow. This might cause a stack . . .)

Anyway, each time your recursive method is called, it pushes the stack, which is to say that it puts a reference to itself onto the stack, so that when the last call to CalculatePi is called, it can unwind all of the rest of the calls.

The stack is not an infinite resource. Each push to the stack eats up a bit of memory, and when you use it all up, you get a stack overflow.

Answer 7

It's not infinite recursion obviously since it stops after 10,000 levels, but it's still not the best idea.

Ten thousand stack levels is an awful lot - the stack is not a massive resource. You should convert it into an iterative solution.

Answer 8

Since you're almost able to run the program, you can just make it use less stack space. Just run in Release mode instead of Debug and it should work.

Answer 9

The iterative code to do this is simply:

private double CalculatePi(int iterations) {
  double pi = 1.0;
  for (int i = iterations - 1; i >= 1; i--) {
    pi = 1 + i / (2.0 * i + 1) * pi;
  }
  return pi * 2.0;
}

Usage:

double pi = CalculatePi(51);

Answer 10

This woudl be the non recursive variant:

        private double CalculatePi(int maxRecursion)
    {
        return 2 * CalculatePi2(maxRecursion, 1);
    }

    private double CalculatePi2(int maxRecursion, int i)
    {
        double product = 1;
        while (i < maxRecursion)
        {
            product = product * (1f + i / (2.0f * i + 1f));
            i++;
        }
        return product;
    }

Answer 11

Iterative version:

public static double CalculatePi(int maxRecursion)
{
    double result=1;
    for(int i=maxRecursion-1;i>=1;i--)
    {
        result=1+i/(2.0*i+1)*result;  
    }
    return result*2;
}

Answer 12

Recursive function calls are almost always a really awful way to do things.

I would simply get the value of pi from a header file/math library.