C/C++ Stackoverflow error in array of 1 million

Question

I am using VC++ 2010. I have written a short program to get Collatz conjecture chain for 1 million numbers in an long int array and get the highest number in series. When I try to run the code, I get stack overflow exception.

How should I get past this?

//Might have took un-needed headers
#include "stdafx.h"
#include "stdio.h"
#include "conio.h"
#include "iostream"
#include "fstream"
#include "string"
#include "list"
using namespace std;


//traverse the array for max term 
long int max_array(long int a[], long int num_elements)
{
    long int i, max=-32000;
    for (i=0; i<num_elements; i++)
    {
        if (a[i]>max)
        {
            max=a[i];
        }
    }
    return(max);
}

//recursive function to calculate and count based on Collatz_conjecture
long int Collatz( long int c1, long int currentcounter)
{
    if ( c1 == 1) return currentcounter;
    if ( c1 % 2 ==0)
    {
        currentcounter++;
        Collatz (c1/2, currentcounter);
    }
    else
    {
        currentcounter++;
        Collatz((3*c1)+1, currentcounter);
    }
}

void main()
{   
    long int  totalcounter[1000000]={0},t1,max;

    for (long  int i=1;i<1000001;i++)
    {
        totalcounter[i]++;
        totalcounter[i]=Collatz(i,totalcounter[i]); 
        printf("Collatz count of no: %li is %li \n",i,totalcounter[i]);
    }
    max = max_array(totalcounter, 1000000);
    printf("The max is %d\n", max);
}

Answer 1

The stack is typically of a fixed, fairly small size - perhaps a few megabytes. You are doing two things which could easily cause too much stack use:

• Creating an automatic array of several megabytes
• Calling a recursive function with no bounds on the recursion depth; unless the compiler is able to optimise the function into a loop, then each recursive call creates a new stack frame, so you will run out of stack if the Collatz path is too long.

The first can be fixed by using a dynamic array for the counters:

std::vector<long int> totalcounter;

or by not storing all the results, just the largest you've found after each iteration.

The second can be fixed by either checking that the compiler does optimise out the recursion, or implementing it iteratively; something like this (untested):

long int Collatz(long int c1)
{
    long int counter = 0;
    while (c1 != 1) {
        ++counter;
        c1 = (c1 % 2 == 0) ? c1/2 : 3*c1+1;
    }
    return counter;
}

(If you do decide to keep your recursive implementation, then you'll need to either pass currentcounter by reference, or update it with the return value of each recursive call and remember to return a value in all cases. Also, your array indexes in main() should run from 0 to N-1, not from 1 to N. And main() must return int, although you can leave out the return statement if you want).