4 ms·

I understand this sentiment, but what simple zero-context function would you choose in place of factorial? You'd want something that's trivially and naturally

by jfb 13y ago

I understand this sentiment, but what simple zero-context function would you choose in place of factorial? You'd want something that's trivially and naturally recursive that doesn't also act on non-primitive types (to avoid having to do a bunch of blahblah introducing the particulars of a given data structure).

IgorPartola 13y ago
How about merge sort or quicksort? Or maybe a binary search? Seems a little more real-worldy. I suppose factorial is a good starting point to illustrate how to construct the function, but an example or two of an actual use case would be so so great.
- jerf 13y ago
  "merge sort or quicksort? Or maybe a binary search?" OK, but couldn't you then still complain that each of those are "Simple, shorter, no overhead from function calls, etc." as while loops?
  - IgorPartola 13y ago
    You might. The problem with doing a binary search in a while loop is that now you have to actually maintain your own stack, which to me seems like it should be left to the runtime. The point of using a recursion is that you can do the same thing as a loop but with less code. Mostly, the problem is that no developer in the last 10 years has ever had to write an efficient factorial function except in a job interview or for a blog post. That is slightly less the case with sorts and searches.
- mck- 13y ago
  Agreed -- I would love to see an example of a binary tree. As a matter of fact, I was struggling with Stack Overflow problems when constructing huge kd-trees recursively. I read this article a week ago, but failed to translate the pure recursive formulation of constructing a tree into a tail-recursive one -- since the recursion goes two ways instead of one Here's an example from Wikipedia: function kdtree (list of points pointList, int depth) { // Select axis based on depth so that axis cycles through all valid values var int axis := depth mod k; // Sort point list and choose median as pivot element select median by axis from pointList; // Create node and construct subtrees var tree_node node; node.location := median; node.leftChild := kdtree(points in pointList before median, depth+1); node.rightChild := kdtree(points in pointList after median, depth+1); return node; }

by jfb 13y ago

IgorPartola 13y ago

How about merge sort or quicksort? Or maybe a binary search? Seems a little more real-worldy. I suppose factorial is a good starting point to illustrate how to construct the function, but an example or two of an actual use case would be so so great.

jerf 13y ago
"merge sort or quicksort? Or maybe a binary search?" OK, but couldn't you then still complain that each of those are "Simple, shorter, no overhead from function calls, etc." as while loops?
- IgorPartola 13y ago
  You might. The problem with doing a binary search in a while loop is that now you have to actually maintain your own stack, which to me seems like it should be left to the runtime. The point of using a recursion is that you can do the same thing as a loop but with less code. Mostly, the problem is that no developer in the last 10 years has ever had to write an efficient factorial function except in a job interview or for a blog post. That is slightly less the case with sorts and searches.
mck- 13y ago
Agreed -- I would love to see an example of a binary tree. As a matter of fact, I was struggling with Stack Overflow problems when constructing huge kd-trees recursively. I read this article a week ago, but failed to translate the pure recursive formulation of constructing a tree into a tail-recursive one -- since the recursion goes two ways instead of one Here's an example from Wikipedia: function kdtree (list of points pointList, int depth) { // Select axis based on depth so that axis cycles through all valid values var int axis := depth mod k; // Sort point list and choose median as pivot element select median by axis from pointList; // Create node and construct subtrees var tree_node node; node.location := median; node.leftChild := kdtree(points in pointList before median, depth+1); node.rightChild := kdtree(points in pointList after median, depth+1); return node; }