Recursive to Iterative

[rmxhaha]

map< int, int > cache;

int count( int n ){
	if( cache[n] != 0 ){
		return cache[n];
	}
	
	if( n == 1 ) return 1;

	
	if( n % 2 == 1 ) 
		cache[n] = 1 + count( 3*n + 1 );
	else
		cache[n] = 1 + count( n / 2 );
	
	return cache[n];
}

I felt a bit stupid right now, I don't know how to turn this recursive function into an iterative...

can someone give me a hint ?

[dhayden]

Returning the right value is fairly easy. Just create a loop and instead of calling count() recursively, assign a new value to n.

But the function also updates cache with the intermediate answers. If you want to do that, then I think you should stick with recursion.

Final note, since cache is a cache of return values for count(), you might make it static inside of count().

[Computergeek01]

Can I ask why you want to? In this context it would just mean A LOT of repetitive and senseless typing. In the interest of academia though; a grossly over simplified definition of recursion is when a function calls itself. Do you see where this function is doing that on Lines 14 and 16? That is where you want to make your changes.

[rmxhaha]

I just return to the realm of "Competitive programming".
This is UVA basic problem
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=36

Yes it is only for training logic.
Not really going for the competition...

I cannot use recursive b/c the stack would be to deep and causes SEGFAULT

I am still thinking ..

int count( int n ){
	if( cache[n] != 0 ){
		return cache[n];
	}
	
	if( n == 1 ) return 1;
	
	int k = n;
	
	int c = 0;
	while( n != 1 ){
		if( cache[n] != 0 ){
			c += cache[n];
			break;
		}
		
		if( n % 2 == 1 ){
			n = 3*n + 1;
		}
		else {
			n /= 2;
		}
		++ c;
	}
	
	
	cache[k] = c;
	return c;
}

But this code doesn't do quite what the recursive version did....

[Little Bobby Tables]

i might be missing something but how is the first count function recursive?

[dhayden]

@Little Bobby Tables, it calls itself at lines 14 and 16.

[Little Bobby Tables]

oh sorry my bad

[ne555]

> I cannot use recursive b/c the stack would be to deep and causes SEGFAULT
http://uvatoolkit.com/problemssolve.php

> 1 999999
1 999999 525

I don't think that that is too deep.

The problem may be in

map< int, int > cache;
int count( int n ){