unt311's blog

iterative code running slower than recursive. Why ?
By unt311, history, 3 years ago, In English

I tried solving problem magic numbers with iterative digit dp. But it runs slower than my recursive solution by more than 200ms.

iterative : link

recursive : link

I also avoided using modulo operations in my iterative code, but am surprised to see it running slower.

Any idea why this happened?

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

There are only $$$O(1)$$$ states which don't have the last 2 values equal to 1, meaning that the recursive solution visits about 4 times less states than the iterative solution(the recursive solution visits about $$$nm$$$ states, while the iterative solution visits about $$$4nm$$$ states).127938045 just adds an if to make sure states that are unreachable don't waste time and that speeds up the solution a lot.

→ Reply