49

Question

What are the possible ways to solve a stack overflow caused by an recursive algorithm?

Example

I'm trying to solve Project Euler problem 14 and decided to try it with a recursive algorithm. However, the program stops with a java.lang.StackOverflowError. Understandably. The algorithm indeed overflowed the stack because I tried to generate a Collatz sequence for a very large number.

Solutions

So I was wondering: what standard ways are there to solve a stack overflow assuming your recursive algorithm was written correctly and would always end up overflowing the stack? Two concepts that came to mind were:

  1. tail recursion
  2. iteration

Are ideas (1) and (2) correct? Are there other options?

Edit

It would help to see some code, preferably in Java, C#, Groovy or Scala.

Perhaps don't use the Project Euler problem mentioned above so it won't get spoiled for others, but take some other algorithm. Factorial maybe, or something similar.

16
  • 3
    Iteration. Memoisation
    – James
    Apr 11, 2013 at 10:50
  • 2
    Obviously, Memoization only works when there actually is repeated calculation. Apr 11, 2013 at 12:06
  • 2
    also worth noting that not all language implementations can do tail recursion optimizations anyway
    – jk.
    Apr 11, 2013 at 12:22
  • 2
    This would probably be better solved with corecursion than recursion. Apr 11, 2013 at 13:31
  • 3
    If you are working from the number less than 1,000,000 and going to 1, the answer to this question involves about 500 steps to reach 1. This should not tax recursion given a small stack frame. --- If you are attempting to solve starting at 1, then following it to 2, 4, 8, 16, {5,32} and go up from there, you are doing it wrong.
    – user40980
    Apr 11, 2013 at 13:51

8 Answers 8

40

Tail call optimization is present in many languages and compilers. In this situation, the compiler recognizes a function of the form:

int foo(n) {
  ...
  return bar(n);
}

Here, the language is able to recognize that the result being returned is the result from another function and change a function call with a new stack frame into a jump.

Realize that the classic factorial method:

int factorial(n) {
  if(n == 0) return 1;
  if(n == 1) return 1;
  return n * factorial(n - 1);
}

is not tail call optimizatable because of the inspection necessary on the return. (Example source code and compiled output)

To make this tail call optimizeable,

int _fact(int n, int acc) {
    if(n == 1) return acc;
    return _fact(n - 1, acc * n);
}

int factorial(int n) {
    if(n == 0) return 1;
    return _fact(n, 1);
}

Compiling this code with gcc -O2 -S fact.c (the -O2 is necessary to enable the optimization in the compiler, but with more optimizations of -O3 it gets hard for a human to read...)

_fact(int, int):
    cmpl    $1, %edi
    movl    %esi, %eax
    je  .L2
.L3:
    imull   %edi, %eax
    subl    $1, %edi
    cmpl    $1, %edi
    jne .L3
.L2:
    rep ret

(Example source code and compiled output)

One can see in segment .L3, the jne rather than a call (which does a subroutine call with a new stack frame).

Please note this was done with C. Tail call optimization in Java is hard and depends on the JVM implementation (that said, I haven't seen any that do it, because it is hard and implications of the required Java security model requiring stack frames - which is what TCO avoids) -- tail-recursion + java and tail-recursion + optimization are good tag sets to browse. You may find other JVM languages are able to optimize tail recursion better (try clojure (which requires the recur to tail call optimize), or scala).

That said,

There is a certain joy in knowing that you wrote something right - in the ideal way that it can be done.
And now, I'm going to get some scotch and put on some German electronica...


To the general question of "methods to avoid a stack overflow in a recursive algorithm"...

Another approach is to include a recursion counter. This is more for detecting infinite loops caused by situations beyond one's control (and poor coding).

The recursion counter takes the form of

int foo(arg, counter) {
  if(counter > RECURSION_MAX) { return -1; }
  ...
  return foo(arg, counter + 1);
}

Each time you make a call, you increment the counter. If the counter gets too big, you error out (in here, just a return of -1, though in other languages you may prefer to throw an exception). The idea is to prevent worse things from happening (out of memory errors) when doing a recursion that is much deeper than expected and likely an infinite loop.

In theory, you shouldn't need this. In practice, I've seen poorly written code that has hit this because of a plethora of small errors and bad coding practices (multithreaded concurrency issues where something changes something outside the method that makes another thread go into an infinite loop of recursive calls).


Use the right algorithm and solve the right problem. Specifically for the Collatz Conjecture, it appears that you are trying to solve it in the xkcd way:

XKCD #710

You are starting at a number and doing a tree traversal. This rapidly leads to a very large search space. A quick run to calculate the number of iterations for the correct answer results in about 500 steps. This shouldn't be an issue for recursion with a small stack frame.

While knowing the recursive solution is not a bad thing, one should also realize that many times the iterative solution is better. A number of ways of approaching converting a recursive algorithm to an iterative one can be seen on Stack Overflow at Way to go from recursion to iteration.

7
  • 1
    I had come across that xkcd cartoon today while surfing the web. :-) Randall Munroe's cartoons are a delight.
    – Lernkurve
    Apr 11, 2013 at 15:26
  • @Lernkurve I noticed the addition of the code edit after I had started writing this (and posted). Do you need other code samples for this?
    – user40980
    Apr 11, 2013 at 15:58
  • No, not at all. It's perfect. Thanks a bunch for asking!
    – Lernkurve
    Apr 11, 2013 at 18:03
  • May I suggest adding this cartoon too: imgs.xkcd.com/comics/functional.png Feb 23, 2015 at 19:45
  • @espertus thank you. I've added it (cleaned up some source generation and added a bit more)
    – user40980
    Feb 24, 2015 at 1:36
17

Keep in mind that the language implementation must support tail recursion optimization. I don't think the major java compilers do.

Memoization means you remember the result of a calculation rather than recalculating it every time, like:

collatz(i):
    if i in memoized:
        return memoized[i]

    if i == 1:
        memoized[i] = 1
    else if odd(i):
        memoized[i] = 1 + collatz(3*i + 1)
    else
        memoized[i] = 1 + collatz(i / 2)

    return memoized[i]

When you're calculating every sequence less than a million, there's going to be a lot of repetition at the end of the sequences. Memoization makes it a quick hash table lookup for previous values instead of having to make the stack deeper and deeper.

1
  • 1
    Very understandable explanation of memoization. Above all, thank you for illustrating it with a code snippet. Also, "there's going to be a lot of repetition at the end of the sequences" made things clear for me. Thank you.
    – Lernkurve
    Apr 11, 2013 at 14:56
10

I'm surprised that no one has mentioned trampolining yet. A trampoline (in this sense) is a loop that iteratively invokes thunk-returning functions (continuation passing style) and can be used to implement tail-recursive function calls in a stack-oriented programming langauge.

This StackOverflow question goes into quite a bit more detail about various implementations of trampolining in Java: Handling StackOverflow in Java for Trampoline

1
  • I thought of this right away as well. Trampolines are a method of for performing tail call optimization, so people are (sorta-almost-maybe) saying it. +1 For the specific reference. Apr 12, 2013 at 0:49
6

If you are using a language and compiler that recognize tail recursive functions and handles them properly (i.e. "replaces the caller in place with the callee"), then yeah, the stack should not grow out of control. This optimization essentially reduces a recursive method to an iterative one. I don't think Java does this, but I know that Racket does.

If you go with an iterative approach, rather than a recursive approach, you are removing much of the need to remember where calls are coming from, and practically eliminating the chance of a stack overflow (from recursive calls anyway).

Memoization is great and can cut down on the overall number of method calls by looking up previously calculated results in a cache, given that your overall calculation will incur many smaller, repeated calculations. This idea is great -- it's also independent of whether or not you are using an iterative approach or a recursive one.

2
  • 1
    +1 for pointing out memoization is also useful in iterative approaches. Apr 11, 2013 at 14:42
  • All functional programming languages have tail call optimization.
    – user4626
    Feb 11, 2014 at 6:00
3

you could create an Enumeration that will replace the recursion... here is an example for calculating faculty doing that... (wont work for big numbers as i only used long in the example :-))

public class Faculty
{

    public static IEnumerable<long> Faculties(long n)
    {
        long stopat = n;

        long x = 1;
        long result = 1;

        while (x <= n)
        {
            result = result * x;
            yield return result;
            x++;
        }
    }
}

even if this is not memoization, this way you will void a stack overflow


EDIT


I am sorry if I upset some of you. My only intention was to show a way how to avoid a stack overflow. I probably should have written a full code example instead of just a small piece of a quickly written and rough code excerpt.

The following code

  • avoids recursion as I use calculate the required values iteratively.
  • includes memoization as Values already calculated are stored away and retrieved if already calculated
  • also includes a stopwatch, so you can see that memoization works properly

...umm... if you run it make sure you set your command shell window to have a buffer of 9999 lines... the usual 300 will not be enough to run through the results of the below program...

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using System.Timers;

namespace ConsoleApplication1
{
    class Program
    {
        static Stopwatch w = new Stopwatch();
        static Faculty f = Faculty.GetInstance();

        static void Main(string[] args)
        {
            Out(5);
            Out(10);
            Out(-5);
            Out(0);
            Out(1);
            Out(4);
            Out(29);
            Out(30);
            Out(20);
            Out(10000);
            Out(20000);
            Out(19999);
            Console.ReadKey();
        }

        static void Out(BigInteger n)
        {
             try
            {
                w.Reset();
                w.Start();
                var x = f.Calculate(n);
                w.Stop();
                var time = w.ElapsedMilliseconds;
                Console.WriteLine(String.Format("{0} ({2}ms): {1}", n, x, time));
            }
            catch (ArgumentException e)
            {
                Console.WriteLine(e.Message);
            }

            Console.WriteLine("\n\n");
       }
    }

I declare * 1 static variable "instance" in the Faculty class to a store a singleton. That way as long as your program is running, whenever you "GetInstance()" of the class you get the instance that has stored all values already calculated. * 1 static SortedList which will hold all the values already calculated

In the constructor I also add 2 special values of the list 1 for inputs 0 and 1.

    public class Faculty
    {
        private static SortedList<BigInteger, BigInteger> _values; 
        private static Faculty _faculty {get; set;}

        private Faculty ()
        {
            _values = new SortedList<BigInteger, BigInteger>();
            _values.Add(0, 1);
            _values.Add(1, 1);
        }

        public static Faculty GetInstance() {
            _faculty = _faculty ?? new Faculty();
            return _faculty;
        }

        public BigInteger Calculate(BigInteger n) 
        {
            // check if input is smaller 0
            if (n < 0)
                throw new ArgumentException(" !!! Faculty is not defined for values < 0 !!!");

            // if value is not already calculated => do so
            if(!_values.ContainsKey(n))
                Faculties(n);

            // retrieve n! from Sorted List
            return _values[n];
        }

        private static void Faculties(BigInteger n)
        {
            // get the last calculated values and continue calculating if the calculation for a bigger n is required
            BigInteger i = _values.Max(x => x.Key),
                           result = _values[i];

            while (++i <= n)
            {
                CalculateNext(ref result, i);
                // add value to the SortedList if not already done
                if (!_values.ContainsKey(i))
                    _values.Add(i, result);
            }
        }

        private static void CalculateNext(ref BigInteger lastresult, BigInteger i) {

            // put in whatever iterative calculation step you want to do
            lastresult = lastresult * i;

        }
    }
}
7
  • 5
    technically this is iteration as you completely removed any recursion Apr 11, 2013 at 12:03
  • that it is :-) and it memoizes the results within the methods variables between each calculation step
    – Ingo
    Apr 11, 2013 at 12:07
  • 2
    I think you misunderstand memoisation, which is when faculties(100) is called the first time it calculates the result and stores it in a hash and returned, then when it is called again the stored result is returned Apr 11, 2013 at 12:21
  • @jk. To his credit, he never actually says this is recursive.
    – Neil
    Apr 11, 2013 at 14:13
  • even if this is not memoization, this way you will void a stack overflow
    – Ingo
    Apr 11, 2013 at 15:13
2

As for Scala, you can add the @tailrec annotation to a recursive method. This way the compiler ensures that tail call optimization actually took place:

So this won't compile (factorial):

@tailrec
def fak1(n: Int): Int = {
  n match {
    case 0 => 1
    case _ => n * fak1(n - 1)
  }
}

the error message is:

scala: could not optimize @tailrec annotated method fak1: it contains a recursive call not in tail position

On the other hand:

def fak3(n: Int): Int = {
  @tailrec
  def fak3(n: Int, result: Int): Int = {
    n match {
      case 0 => result
      case _ => fak3(n - 1, n * result)
    }
  }

  fak3(n, 1)
}

compiles, and tail call optimization took place.

1

One possibility which have not been mentioned yet is to have recursion, but without using a system stack. Of course you can overflow your heap as well, but if your algorithm really need backtracking in one form or another (why using recursion at all otherwise?), you've got no choice.

There are stackless implementations of some languages, e.g. Stackless Python.

0

Another solution would be to simulate your own stack and not rely on the implementation of the compiler + runtime. This is not a simple solution nor a fast one but theoretically you'll get StackOverflow only when you're out of memory.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.