Personal computing discussed
Moderators: renee, SecretSquirrel, just brew it!
derFunkenstein wrote:But how often will I run into this? I'm guessing the answers will vary and the truth starts with "it depends" but I figured I'd ask you guys. How much recursion do you do?
Redocbew wrote:There are some real oddballs(like the Ackermann function)
public int bensFactorial (int x)
{
if (x > 1)
{
//recursive case:
return bensFactorial(x-1) * x;
}
else /*base case*/
return 1;
}
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"
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;
}
Get-ADGroupMember "GroupName" -Recursive
Losergamer04 wrote:I do a lot of PowerShell. I won't even try to hold a candle to what you guys do.
DancinJack wrote:Recursion was the first concept in my C++ class as a freshman in college that really got me thinking. It was kinda tough at the time, and is still tough in some cases, but pretty cool and useful too.
So how many times did you type something like this Ben? (not C++ btw)
public static int factorial(int n)
{
//figure out the base case - factorial of 1 is 1.
if (n==1) return 1;
//not the base case, so call itself again.
return n * factorial(n-1);
}
Losergamer04 wrote:I do a lot of PowerShell. I won't even try to hold a candle to what you guys do. That said, smarter people than I (like some of you actual programmers) wrote a very use recursive function I use regularly (weekly?) when I search AD group membership and want all the users in our horrid mess of nested groups.Code: Select allGet-ADGroupMember "GroupName" -Recursive
lycium wrote:Speaking in even greater generality, most people employ a recursive algorithm in general problem solving: "divide and conquer".
An example that we've probably all experienced: when a non-technical family member asks you simply, "why is my computer acting up?", the range of possible causes is so large that you more or less have to engage in a process of splitting the possible causes up into groups, ruling out ones that do not seem to be the problem (pruning the tree), and further investigating ones that seem like they might be the cause, etc (recursively).
In this way, with effective subdivision and pruning, you can find the problem in O(log N) time instead of trying everything, or O(N).