Why do top guys favor array-based versus recursive DP?

Правка en1, от royappa, 2016-04-14 19:34:30

This is a question about psychology, not about the best way to program something.

I have often felt that the top contestants seem to prefer writing DP solutions using for-loops and arrays, instead of memoized recursive functions.

Certainly there are times when one or the other method is "right" based on the density of the search space, depth of recursion etc. But often it doesn't matter, and in those cases, the top programmers overwhelmingly use loop+array. This seems counterintuitive to me because the loop+array approach often has corner cases to think about regarding array initialization and loop boundaries. Programming with a recursive function, on the other hand, seems to correspond more "naturally" with a mathematical expression of a recursive formula. The base cases are much simpler and correspond more directly with the math of the problem.

For a silly example, take f(n) = { if (n == 0) return 1; else return n*f(n-1); }, this is almost like the mathematical way of writing it (like this notation from Wikipedia ).

But in no math book would you see f[0] = 1; for (int i = 1; i <= n; i++) { f[i] = i*f[i-1]; }. That loop is not "the math way". Yet the top programmers seem to favor loops.

To test this theory I performed a rigorous scientific experiment. Here is the problem for topcoder TCHS 44 medium: https://community.topcoder.com/stat?c=problem_statement&pm=8250&rd=10795

It has a simple recursive solution. I then looked at ALL the red user submissions in the practice room, 32 total. This screenshot shows that the top 12 all used array+loop. The 13th used memoization (and his solution was faster — because even for those guys I think saving a few seconds thought on boundary cases makes a difference).

Of the 32 "red" solutions, only 6 used recursive functions.

We know the top guys are highly mathematically minded, so why don't they favor that style in their programming? Do they start out that way and then turn to array/loops after practicing lots of problems? Or do they start out writing like that the moment they encounter recursive solutions because that is the way their mind things? (bottom-up instead of top-down)? Do they hate writing a separate function when you can do everything in the main() ?

Would be curious to get anybody's thoughts, if they more naturally write loop+array, why they do so. And I don't know if it's just "top" programmers who do this or some set of people across all ranks. I mainly study top programmers solutions to learn, so my sample is obviously biased.

Теги programming, dp, recursion

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский royappa 2016-04-14 19:34:30 2721 Initial revision (published)