derFunkenstein wrote:Is it likely that anything using a "tree" structure (directories, devices, whatever else) should naturally use recursion? Maybe that could be abstracted more into "anything where you do something, and depending on the results you might do it again with different data"
As a general rule, I would say "probably". An time the result of an operation on a dataset is a subset on which you will perform the same operation until an end condition is met, then recursion is a viable and probably preferred solution. Just like any other programming approach, once you get it, you will start to see everything as a recursive problem. This can be bad, of course. But, IMHO, recursion is one of those things that is either incredibly easy to apply to a problem (correct solution) or very hard (not correct solution).
If you can represent the data as a tree (as others have said), of any sort, the the solution will involve recursion for all but the smallest data set. One thing to think about is that the nodes in the tree can have any number of branches. To give a real world example, I once wrote a program the had to rapidly search UUIDs for a match and return associated data. The UUIDs were stored as a 32 character string. Speed was the driving factor so memory was traded for speed. Each node in the tree represented one character in the UUID. Each node had 16 entries pointing to the next node, depending on what the hex value was. You would walk the tree, following the nodes that match UUID characters until you reached a leaf (no more nodes). Leaf nodes would also contain any remaining UUID string for that node, which you could compare against your search string. The end result was that you could find any UUID's data, or the lack of a match, within 32 comparisons and 32 node traversals. No matter how big the dataset got, the search was always bounded to that set of operations. Only memory usage would grow (and pretty quickly), but speed was the absolute requirement.
Code for searching for a UUID is approximately the below (written as old fashioned C with C++ style comments and pointers and other magic):
struct data * findByUuid(char *uuid, struct uuidTree *tree) {
//convert the current UUID character to a hex value.
uint8_t hexVal=*uuid-'0';
//If the value has a branch, then we recurse through the nodes
//we pass in the next character in the UUID string and use the node down
//the branch as our starting point
if(tree->branch[hexVal]) {
return findByUuid(uuid++, tree->branch[hexVal]);
}
//no more nodes, we need to check any remainder of the UUID string against the
//remainder stored as part of the node. If they match, then we found our UUID.
if(strcmp(uuid, tree->uuid)==0 {
return tree->data;
}
return 0;
}
Symmetry can be defined in terms of recursion, but it's a somewhat artificial definition since it always terminates after N steps (for N-fold symmetry) and basically amounts to iteration rather than "real" recursion (as with the factorial computation).