title: Convert recursive function to iterative function
body: <p>Although this may seem like a duplicate (maybe it is but I haven't found a solution to this version of the problem yet), I don't think it is.</p>
  
  <p>Below is my recursive function which blows python's recursion limit and I'd need to make it iterative instead but I'm having issues seeing how it could be possible.</p>
  
  <pre><code>def countChain(n, cache):
      if cache[n] != -1:
          return cache[n]
  
      if n % 2 == 0:
          cache[n] = 1 + countChain(n / 2, cache)
      else:
          cache[n] = 2 + countChain((3 * n + 1) / 2, cache)
  
      return cache[n]
  </code></pre>
  
  <p>Note that here my cache list has 1 million elements in it... (which is why the recursion kills python). I've seen people use an accumulator to do the job but here I'm not returning directly the result of the recursive call which makes this idea hard to implement.</p>
  
  <p><strong>EDIT</strong></p>
  
  <p>the first recursive call should have been <code>cache[n] = 1 + countChain(n / 2, cache)</code> instead of <code>cache[n] = 1 + countChain(n, cache)</code></p>
  
  <p><strong>EDIT 2</strong></p>
  
  <p>Someone asked for example data so I will simply type in the whole code (not that long) for a better understanding.</p>
  
  <pre><code>import time
  import sys
  import math
  
  def main():
      target = int(sys.argv[1])
  
      start = time.time()
      longest = 0
      answer = -1
  
      for i in range(int(target/2), target):
          if countChain(i) &gt; longest:
              longest = countChain(i)
              answer = i
  
      print("Result = ", answer, " in ", (time.time() - start), " seconds")
  
  def countChain(n,cache={1:0}):
      if n not in cache: 
          if n % 2 == 0:
              cache[n] = 1 + countChain(n//2, cache)
          else:
              cache[n] = 2 + countChain((3 * n + 1) // 2, cache)
      return cache[n]
  
  if __name__ == "__main__":
      main()
  </code></pre>
  
  <p>The usual input is 1000000</p>
  
  <p>Also the else should have been 2 + ...</p>