Stack Overflow Caused by Recursive Function

Stack overflow caused by recursive function

Whenever you call a function, including recursively, the return address and often the arguments are pushed onto the call stack. The stack is finite, so if the recursion is too deep you'll eventually run out of stack space.

What surprises me is that it only takes 4793 calls on your machine to overflow the stack. This is a pretty small stack. By way of comparison, running the same code on my computer requires ~100x as many calls before the program crashes.

The size of the stack is configurable. On Unix, the command is ulimit -s.

Given that the function is tail-recursive, some compilers might be able to optimize the recursive call away by turning it into a jump. Some compilers might take your example even further: when asked for maximum optimizations, gcc 4.7.2 transforms the entire function into:

int returnZero(int anyNumber) {
  return 0;
}

This requires exactly two assembly instructions:

_returnZero:
        xorl    %eax, %eax
        ret

Pretty neat.

How to fix a stack overflow error caused by recursive functions? C++

Your code is an example of tail recursion because the recursive calls are the last thing executed in each function. Tail recursion is easy to transform into a non-recursive loop. The following code is the equivalent to the code you have and doesn't use recursion at all.

static bool orient_face(HEF *face)
{
    for (;;)
    {
        assert(face->oriented);
        HE *edge = face->edge;
        if (edge->flip == NULL)
            return 1;
    }
}

static bool build_HE(he::Mesh_Data *mesh,
                     std::vector<HEV*> *hevs,
                     std::vector<HEF*> *hefs)
{
     // process mesh data
     // ...

     return orient_face(first_face);
}

As some programmer dude pointed out, the code is effectively a no-op (excepting the assert, but I'm assuming that's just a debugging detail, and not the point of the code). So unless there's something else going on you can delete it completely.

The details matter.

How can I debug my recursive function that's causing stack overflow error?

good question. First, I think that a recursive solution isn't ideal here. I got it working for the inputs you gave, but considering how small PAGEWIDTH is, you'll likely run into issues with larger inputs. Using a loop would make your life easier and result in a more reliable function.

That said, your issue lies in the recursive call you make in the fold() function, you are providing the wrong start index. This means you don't move forward in the line with each call. Also, you don't clearly define a base case (i.e. when to end the recursion). You can do this by modifying your for loop conditions or passing the string length (n) to the function and checking whether start > n.

Checking base case and the recursive call is always a good place to start when debugging recursive functions. This is normally where my issues come from and it's really easy to assume you did them correctly and overlook them while debugging.

I'm not sure what you are looking for in terms of an answer, but if those suggestions don't get you any closer, I pasted a fix in a pastebin here. I didn't post it here in case you wanted to solve it on your own.

Hope that works, let me know if there's something I missed.

Is my recursive function failing due to a stack overflow? If yes, given my function definition, is it normal?

This is likely a stack overflow, function hasView is called cursively with a depth roughly equal to count and the stack has to store count adresses which could exceed the stack size for huge numbers.

More details in another post: BAD_ACCESS during recursive calls in Swift

Please note that what you implemented seems to be a running maximum in reverse order returning the indices and this can implemented more efficiently without overflow like this:

func runningMax(_ arr: [Int]) -> [Int] {
    var max = 0
    var out = [Int]()

    for (i, element) in arr.enumerated().reversed() {
        if element > max {
            max = element
            out.append(i)
        }
    }

    return out.reversed()
}

I compared this with your algorithm and the outputs seems to be identical. I also tested with larges values up to 100,000,000 and it is fine.

Returned array does not need to be optional, if the input array is empty so do the output array.

how many recursive function calls causes stack overflow?

I want to know that is this normal?

Yes. There's only so much stack size.

In the code below, removing local variable neighbor can prevent from stack overflow?

No. Even with no variables and no return values the function calls themselves must be stored in the stack so the stack can eventually be unwound.

For example...

void recurse() {
    recurse();
}

int main (void)
{
    recurse();
}

This still overflows the stack.

$ ./test
ASAN:DEADLYSIGNAL
=================================================================
==94371==ERROR: AddressSanitizer: stack-overflow on address 0x7ffee7f80ff8 (pc 0x00010747ff14 bp 0x7ffee7f81000 sp 0x7ffee7f81000 T0)
    #0 0x10747ff13 in recurse (/Users/schwern/tmp/./test+0x100000f13)

SUMMARY: AddressSanitizer: stack-overflow (/Users/schwern/tmp/./test+0x100000f13) in recurse
==94371==ABORTING
Abort trap: 6

In general how many recursive function calls causes stack overflow?

That depends on your environment and function calls. Here on OS X 10.13 I'm limited to 8192K by default.

$ ulimit -s
8192

This simple example with clang -g can recurse 261976 times. With -O3 I can't get it to overflow, I suspect compiler optimizations have eliminated my simple recursion.

#include <stdio.h>

void recurse() {
    puts("Recurse");
    recurse();
}

int main (void)
{
    recurse();
}

Add an integer argument and it's 261933 times.

#include <stdio.h>

void recurse(int cnt) {
    printf("Recurse %d\n", cnt);
    recurse(++cnt);
}

int main (void)
{
    recurse(1);
}

Add a double argument, now it's 174622 times.

#include <stdio.h>

void recurse(int cnt, double foo) {
    printf("Recurse %d %f\n", cnt, foo);
    recurse(++cnt, foo);
}

int main (void)
{
    recurse(1, 2.3);
}

Add some stack variables and it's 104773 times.

#include <stdio.h>

void recurse(int cnt, double foo) {
    double this = 42.0;
    double that = 41.0;
    double other = 40.0;
    double thing = 39.0;
    printf("Recurse %d %f %f %f %f %f\n", cnt, foo, this, that, other, thing);
    recurse(++cnt, foo);
}

int main (void)
{
    recurse(1, 2.3);
}

And so on. But I can increase my stack size in this shell and get twice the calls.

$ ./test 2> /dev/null | wc -l
174622
$ ulimit -s 16384
$ ./test 2> /dev/null | wc -l
349385

I have a hard upper limit to how big I can make the stack of 65,532K or 64M.

$ ulimit -Hs
65532

Recursive function causes stack overflow

You have no terminating condition for your recursion, so it runs forever.

It sounds like maybe you don't have a good grasp of recursion, so I'd like to start with something a little simpler, the Fibonacci sequence.

Any time we define a function in terms of recursion, we need to first define a base case(s). In the case of Fibonacci, we have 2 base cases:

F(0) = 0
F(1) = 1

That says, in english, "F of 0 is 0, F of 1 is 1". Or even more simply, if we pass 0 to function F, we will get 0 back. If we pass 1, we will get 1 back.

Once we have the base cases defined, then we need to look for a recurrence relation. In the case of Fibonacci, we have the following recurrence:

F(n) = F(n-1) + F(n-2)

So for n >= 2, we can use the above recurrence. Why? Well, lets try it for n = 2.

F(2) = F(n-1) + F(n-2)
     = F(1) + F(0)
     = 1    + 0
     = 1

So now we know that the answer to F(2) is 1. And what's more, we can now compute the answer to F(3). Why? Well, what do we need to compute F(3)? We need F(2) and F(1). We now have both of those answers since F(1) is a base case, and we just solved F(2) above.

So, now let's try to write a piece of pseudo code to solve F.

function F(int n) {
  // handle base cases
  if (n equals 0)
    return 0
  if (n equals 1)
    return 1

  // recurrence
  return F(n-1) + F(n-2);
}

Note that in a recursive function, we always handle the base cases at the beginning of the function. We cannot define this recurrence if we don't have base cases in place, otherwise, we will have no terminating condition for our recurrence. So that's why you always put the base cases at the beginning of the function.

Now, given the above explanation, another good exercise would be to write a recursive function for the factorial function. So, follow these steps:

1. Define the base case (use wikipedia article for hints).
2. Define recurrence in terms of base case
3. Write pseudo code to solve the recurrence, and be sure to put base case(s) at beginning of function, and recurrence at end.

Once you grasp these steps, then moving on to the power recurrence should make much more sense to you.

---

Related Topics