Stack Overflow with recursion implementation

[Darkenor]

Hi Everyone,

I'm having a pretty serious issue with stack overflow and recursion. I'm trying to solve Euler problem 14. My implementation works, but when I loop the function that recursively determines the solution it causes a stack overflow and the program crashes. Anybody give me some advice of how I can get this to stop? I've tried just about everything I know.

//The following iterative sequence is defined for the set of positive integers:
//
//n  n/2 (n is even)
//n  3n + 1 (n is odd)
//
//Using the rule above and starting with 13, we generate the following sequence:
//
//13  40  20  10  5  16  8  4  2  1
//It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
//
//Which starting number, under one million, produces the longest chain?
//
//NOTE: Once the chain starts the terms are allowed to go above one million.

#include <iostream>

using namespace std;

int chainlength(int);
int chainlength_i(int, int);

int main()
{
	int temp =0;
	int count =0;
	int value =0;
	
	
	
	for (int x=3; x<1000000; x++)
	{
		temp = chainlength(x);
		
		if (temp > count)
		{
			count = temp;
			value = x;
		}
	}

	cout<<"The count is: "<<count<<"\n";
	cout<<"The value is: "<<value<<"\n";
	return 0;
}

int chainlength(int number)
{
	if (number==1)
	{
		return 1;
	}
	else
	{
		return chainlength_i(number, 0);
	}
}

int chainlength_i(int n, int len)
{
	if (n==1)
	{
		return len;
	}

	len++;
	if (n%2==0)
	{
		n = n/2;
		return chainlength_i(n, len);
	}
	else
	{
		n = 3*n +1;
		return chainlength_i(n, len);
	}

}

[Disch]

Maybe try using an iterative solution instead of a recursive one?

Recursion burns through stack space by nature. If you're going deep enough to cause stack overflows then a recursive solution is probably a bad way to go.

[Darkenor]

Update:

Moments after I pasted this I changed "int" to __int64 (just for giggles) and it worked.

Two questions, then:

1. The largest count is under a thousand and the largest value is under a million - why was an _int64 necessary?

2. Is the program still flawed?

[Computergeek01]

I'm pretty sure that 32-bit integers like 'x' in line 30 don't count up to a million.

[Darkenor]

No,

INT_MIN

Minimum value for a variable of type int.

–2147483648

INT_MAX

Maximum value for a variable of type int.

2147483647

[Computergeek01]

So I missed a place or two :p

I recognise this formula, this is that "Unsolved Number Theory" crap isn't it? What are you trying to do? Prove that math exists? Let's try to just iterate this by hand for I don't know three or four passes. Take and record each return from your second function there and put them on a graph, you will see what is called a "trend" starting to form in the overall progress of the line. It will always go up and there is no situation in your little formula here where it could ever go down.

Please tell me what is the facination with this stuff?

[ne555]

Use a dynamic approach (how much time it takes to your program to output the solution?)

The largest count is under a thousand and the largest value is under a million - why was an _int64 necessary?

if odd 3*n+1. You divide by 2, but multiply by 3.
56991483520 is the maximum number that gets into the function

[Darkenor]

Ne555-

Thanks - that helps my sanity some. Although, I don't see where you got 5699148520?

3 * 999999 +1 = 2999998 ?

On the dynamic solution, I'm thinking about rewriting it using a dynamic programming language like Python or Haskell. But do you have a recommendation on C++?

[ne555]

It's the sequence that starts with 704511.
http://en.wikipedia.org/wiki/Dynamic_programming You calculate many values several times, if you cache the result your program will be faster.