Without using recursion how can a stack overflow exception be thrown?

Question

Without using recursion how can a stack overflow exception be thrown?

Answer 1

Declare an ENORMOUS array as a local variable.

Answer 2

If you call enough methods, a stack overflow can occur anytime. Although, if you get stack overflow errors without using recursion, you may want to rethink how you're doing things. It's just so easy with recursion because in an infinite loop, you call a ton of methods.

Answer 3

Every method call that has not yet returned consumes some stack space. (Methods with more local variables consume more space.) A very deep call stack can result in stack overflow.

Note that on systems with limited memory (mobile devices and such) you don't have much stack space and will run out sooner.

Answer 4

Since no one else has mentioned it:

throw new System.StackOverflowException();

You might do this when testing or doing fault-injection.

Answer 5

If you're talking about C++ with a reasonable standard library, I image that this would work:

while (true) {
    alloca(1024 * 1024); // arbitrary - 1M per iteration.
}

Details on alloca.

Answer 6

Short answer: if you have an object which calls an internal object, you increase the stack trace by 1. So, if you have 1000s of objects nested inside one another, each calling its internal object, eventually you'll get a stack overflow.

Here's a demonstration of how to generate primes using nested iterators:

using System;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            Program p = new Program();

            IEnumerator<int> primes = p.AllPrimes().GetEnumerator();
            int numberOfPrimes = 1000;
            for (int i = 0; i <= numberOfPrimes; i++)
            {
                primes.MoveNext();
                if (i % 1000 == 0)
                {
                    Console.WriteLine(primes.Current);
                }
            }
            Console.ReadKey(true);
        }

        IEnumerable<int> FilterDivisors(IEnumerator<int> seq, int num)
        {
            while (true)
            {
                int current = seq.Current;
                if (current % num != 0)
                {
                    yield return current;
                }
                seq.MoveNext();
            }
        }

        IEnumerable<int> AllIntegers()
        {
            int i = 2;
            while (true)
            {
                yield return i++;
            }
        }

        IEnumerable<int> AllPrimes()
        {
            IEnumerator<int> nums = AllIntegers().GetEnumerator();
            while (true)
            {
                nums.MoveNext();
                int prime = nums.Current;
                yield return prime;

                // nested iterator makes a big boom     
                nums = FilterDivisors(nums, prime).GetEnumerator();
            }
        }
    }
}

There's no recursion, but the program will throw a stack overflow exception after around 150,000 primes.

Answer 7

The following applies to Windows, but most OSs implement this in a similar fashion.

The short answer is: if you touch the last guard page, it will throw.

An exception of type EXCEPTION_STACK_OVERFLOW (C00000FD) is raised when your application touches the bottom page of the stack, that is marked a PAGE_GUARD protection flag, and there is no room to grow the stack (commit one more page), see How to trap stack overflow in a Visual C++ application.
The typical case when this happens is when the stack has grown as the result of many function frames on the stack (ie. out of control recursion), as the result of fewer frames but very large frame sizes (functions with a very large local scoped object) or by explicitly allocating from the stack with _alloca.
Another way to cause the exception is to simply intentionally touch the guard page, eg. by dereferencing a pointer that points into that page. This can happen due to a variable initializion bug.

Stack overflows can occur on valid execution paths if the input causes a very deep nesting level. For instance see Stack overflow occurs when you run a query that contains a large number of arguments inside an IN or a NOT IN clause in SQL Server.

Answer 8

Easiest way to make a StackOverflowException is the following:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            SomeClass instance = new SomeClass();
            string name = instance.Name;
        }
    }

    public class SomeClass
    {
        public string Name
        {
            get
            {
                return Name;
            }
        }
    }
}

Answer 9

You can run out of stack space without infinite recursion just by having bounded recursion that exceed the stack space (yes it's still recursion).

One example is trying to recursively process a very large binary tree that is pathologically unbalanced (i.e. it looks like a linked list).

Answer 10

int main()
{
  //something on the stack
  int foo = 0;
  for (
    //pointer to an address on the stack
    int* p = &foo;
    //forever
    ;
    //ever lower on the stack (assuming that the stack grows downwards)
    --p)
  {
    //write to the stack
    *p = 42;
  }
}