Recursive to Iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19


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 ?
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().
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.
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 ..
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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....
Last edited on
i might be missing something but how is the first count function recursive?
@Little Bobby Tables, it calls itself at lines 14 and 16.
oh sorry my bad
> 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
1
2
map< int, int > cache;
int count( int n ){
Registered users can post here. Sign in or register to post.