monstermceldritch's blog

Recursive vs Iterative Implementations
By monstermceldritch, history, 11 months ago, In English

As I practice competitive programming more and more (and thus implement more and more algorithms), I've begun to have somewhat of a worry that I'm developing the bad habit of favoring recursive implementations over iterative ones. I've mainly implemented DFS/DP/Backtracking recursively this far, and that has made those methods of implementation come much more naturally to me. However, pretty much all study material recommends iterative solutions over recursive ones for the lower constant factors they usually have. This has made me wonder if it would be worth pushing myself to think of the iterative implementations instead of the (to me, more intuitive) recursive ones when solving problems. Has the difference in complexity between the two ever made a difference in competitive programming contests? What about outside of the CP scene? In working environments where efficiency is a major concern, are iterative solutions generally that much better than recursive ones?

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

»
11 months ago, hide # |
 
Vote: I like it +28 Vote: I do not like it

Recursion's downsides is that it is usually slower and has the risk of stack overflow in certain languages (Java I'm pretty sure).

Iterative is usually preferred (like using BFS over DFS whenever possible, also DP) since it is usually faster, but it also gives you less room to solve more complex problems.

Sometimes, a solution requires memoization instead of bottom-up DP in which you would want to use recursion.

DFS should pretty much always use recursion since usually you want to perform some operation when coming back up the recursive calls (especially with Tree DFS/Tree DP).

→ Reply
»
11 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

If you think about it, it makes sense why iterative would be faster, right? You're removing the overhead of running a topological sort from the computer, and putting it on yourself instead.

In most standard dynamic programming problems, finding a toposort is trivial, $$$(a, b)$$$ comes before $$$(c, d)$$$ if $$$a \le c$$$ and $$$b \le d$$$ is the most common pattern. However, for things like dfs/bfs where you're explicitly given a graph rather than it arising intrinsically from the problem constraints, the topological sort is obviously more complicated.

To answer your question, I do think it's worth at least considering trying to think iteratively where it's applicable. It's more work for you, but the speed benefits are insane. Compare the speed of an iterative segment tree to that of a recursive one, or a memoized dp to an iterative one, iterative wins by a long shot.

→ Reply
»
11 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by monstermceldritch (previous revision, new revision, compare).

→ Reply
»
11 months ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

There are situations when only iterative DP is applicable. For example, in some DP problems you need to maintain all calculated DP values in some data structure and transfer from multiple states to one state at the same time. I don't think you can always find a intuitive recursive DP implementation in them.

→ Reply
»
11 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

The constant factor does not have a particularly severe impact on the final efficiency, especially when designing complex transfers.

You can add inline before your function to improve efficiency if you use c++.

→ Reply