### Recursive to Iterative

 ``12345678910111213141516171819`` `````` 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.
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 ..
 ``1234567891011121314151617181920212223242526272829`` ``````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.
 ```> 1 999999 1 999999 525```
 ``12`` ``````map< int, int > cache; int count( int n ){``````