2

I have defined a basic list structure, and a simple insert function, and a search function. The code is below:

////////////////////////////////////////////////
typedef struct list
{
  int item;
  struct list *next;
}List;

////////////////////////////////////////////////
List * search_list(List * l, int i)
{
  if(NULL == l) 
    return(NULL);

  if(i == l->item)
    return l;
  else
    return search_list(l->next, i);
}

////////////////////////////////////////////////
void insert_list(List ** l, int i)
{
  List * p = new List();
  p->item = i;
  p->next = *l;
  *l = p;
}

My main loop to test it, looks like this:

int main(int, char* argv[]) 
{
     List * mylist = new List();

     for(int i = 0; i < 8000; i++)
     {
         insert_list(&mylist,i);
     }

     int val = 2000;
     List * s = search_list(mylist, val);
     return 0; 
}

When val is 4000, the program completes ok. But when val is 2000, i.e. 2000 indexes further down the list, Visual Studio terminates with a stack overflow.

Is the number of recursive calls in search_list() causing a stack overflow? How can I get rid of this error?

patchwork
  • 1,161
  • 3
  • 8
  • 23
  • I found this question, http://stackoverflow.com/questions/15976333/stack-overflow-caused-by-recursive-function?rq=1 . It seems there is no straightforward way to increase stack and this kind of function should be avoided. The code is taken from Skiena's Algorithm Design Manual. – patchwork Jan 09 '14 at 18:54
  • does it _have_ to be recursive? (i.e. is this homework?) Normally, you would not use a recursive method for a search like this, beacuse of this exact problem. You are recursing ~6000 levels deep when searching for 2000. my answer depends on that. – Corley Brigman Jan 09 '14 at 18:54
  • @Corley, Well I've taken code from a textbook ( no it's not homework, I'm just studying stuff myself ). It doesn't have to be recursive no, but I'd expect Skiena's 10 year old code not to crash my laptop. – patchwork Jan 09 '14 at 18:56
  • well, if it has code like that, i definitely wouldn't use it! (and yeah, i would think you could recurse farther than that, but it's rare that you would recurse even a 10th of that in any normal application). that said, there may be a compiler option to increase the stack size, if you're determined to go this way. – Corley Brigman Jan 09 '14 at 19:00
  • 2
    If you compile it with optimization allowed a clever compiler shall optimize the tail-recursion into a loop. Maybe this is what the example demonstrates? – Marian Jan 09 '14 at 19:10
  • nemetroid correctly changed the tag to C++ instead of C. Don't mix up C and C++, these are different languages. In the case here, since you want to use `new` also provide a constructor to your class, otherwise `new` makes not much sense. – Jens Gustedt Jan 09 '14 at 19:19

3 Answers3

3

Recursive algorithms should only be used if the depth is strictly limited or the algorithm has no more than O(logN) complexity. If that's not the case then you always risk stack overflow. Yours doesn't meet the complexity requirement, it is O(N).

Visual Studio doesn't exactly help avoid the crash when you run your program with default Debug build settings. For one, the tail recursion optimization isn't enabled, that requires Release build settings so the optimizer is turned on. For another, the Edit + Continue feature allocates a bunch of extra stack space for a function. It is available in case you add a local variable to the function while debugging.

You can easily turn that off. Project + Properties, C/C++, General, change the Debug Information Format setting to "Program Database (/Zi)". Your program will no longer crash.

Hans Passant
  • 922,412
  • 146
  • 1,693
  • 2,536
1

There is one thing your compiler should have told you: This recursive invocation of search_list doesn't return anything. Didn't you get a warning about this? And using recursion here really is a bad idea, better replace it with some kind of loop. One reason of course is excessive stack usage, another one is debugging sucks with that kind of recursion.

pentadecagon
  • 4,717
  • 2
  • 18
  • 26
0

Besides your stack overflow error, you should check the following. You are not initializing the values of the first allocated List instance at main(), pointed by mylist.

List * mylist = new List();

What your current code does is it passes an "empty" List instance at the first call, that can have an invalid next value. This will be your last List instance in the linked list.

You should do this instead:

List * mylist = NULL;

This will assure you last List instance in the list has a next with NULL value.

ericbn
  • 10,163
  • 3
  • 47
  • 55
  • Interesting, but then that means the pointer to pointer to a `List` needs changing also. – patchwork Jan 09 '14 at 19:13
  • You don't need to change anything else. Setting `mylist = NULL;` and calling `insert_list(&mylist,i);` will simply make `p->next = *l;` act as `p->next = NULL;`, since `*l` is `NULL` at that point. – ericbn Jan 09 '14 at 19:16