Personal computing discussed

Moderators: SecretSquirrel, just brew it!

 
derFunkenstein
Gold subscriber
Gerbil God
Topic Author
Posts: 24256
Joined: Fri Feb 21, 2003 9:13 pm
Location: Comin' to you directly from the Mothership

How recursive is the real world?

Mon Mar 27, 2017 1:42 pm

It finally happened. A topic in one of my classes covered something where I don't get the real-world application: recursion. Maybe it's just the examples that we used, though. I get *how* to do it, at least at a basic level. I did the homework unaided and I wedged it into a recursive format. Examples included:

Computing factorials (done in class)
Computing exponents (done on our own in class)
Counting the number of vowels in a string (part of the homework)
Evaluating whether a numeric string included any odd numbers (also in the homework)
Tower of Hanoi

I get the examples, and in the Tower of Hanoi I can see that it basically has to be recursive. For all the rest I could easily see how to do it in my head with loops instead, so it seems forced. 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?
I do not understand what I do. For what I want to do I do not do, but what I hate I do.
 
Glorious
Gold subscriber
Grand Admiral Gerbil
Posts: 10767
Joined: Tue Aug 27, 2002 6:35 pm

Re: How recursive is the real world?

Mon Mar 27, 2017 1:55 pm

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?


Directory traversal is a real-world application. Doing that recursively is typically more intuitive.
 
just brew it!
Gold subscriber
Administrator
Posts: 50802
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Re: How recursive is the real world?

Mon Mar 27, 2017 2:04 pm

Yeah, most of the examples typically used to teach recursion are simple enough that an iterative soulution would be preferred in practice.

Maintaining of B-Tree (and similar) indices is a good example of a real-world problem where recursion can be used to arrive at a more straightforward solution than an iterative one. Any time you've got state at each step that would need to be explicitly saved and restored as part of an iterative solution, recursion may be appropriate. With a recursive solution you're basically using the function call stack to implicitly do the saving/restoring of state for you, instead of implementing a stack structure explicitly.

OTOH, you also need to be wary of pathological data sets which can result in excessive recursion depth. Classic example of this is a naive implementation of quicksort, when fed an already sorted input. (This is not an issue for B-Tree structures, since the self-balancing nature of B-Trees implicitly puts an upper bound on the maximum recursion depth.)
Nostalgia isn't what it used to be.
 
Redocbew
Gold subscriber
Gerbil Jedi
Posts: 1548
Joined: Sat Mar 15, 2014 11:44 am

Re: How recursive is the real world?

Mon Mar 27, 2017 2:36 pm

Building out navigation is the last place I remember using recursion. I could have done it iteratively, but the data sets I was working with were small, and it reduced the amount of code I had to write. :P

There are some real oddballs(like the Ackermann function) once you get into problems which really do require a recursive approach, so simple examples like that are pretty common. Like JBI said, there are points for and against using recursion it just depends on the complexity of the solution, and the problem you're trying to solve.

I read a book a while ago called The Recursive Mind. The premise is that our ability for recursion is what sets our minds apart which I thought was interesting.

Now you need this tshirt.

http://www.thinkgeek.com/product/b2ae/
Do not meddle in the affairs of archers, for they are subtle and you won't hear them coming.
 
Waco
Gold subscriber
Minister of Gerbil Affairs
Posts: 2263
Joined: Tue Jan 20, 2009 4:14 pm
Location: Los Alamos, NM

Re: How recursive is the real world?

Mon Mar 27, 2017 2:46 pm

Recursion is common, but probably less than you'd think. It's very easy to screw up a recursive algorithm (or the dataset you may be applying it to) and end up essentially infinitely recursing and crashing your application/machine.
Z170A Gaming Pro Carbon | 6700K @ 4.5 | 16 GB | GTX Titan X | Seasonix Gold 850 | XSPC RX360 | Heatkiller R3 | D5 + RP-452X2 | Cosmos II | Samsung 4K 40" | 480 + 240 + LSI 9207-8i (128x8) SSDs
 
derFunkenstein
Gold subscriber
Gerbil God
Topic Author
Posts: 24256
Joined: Fri Feb 21, 2003 9:13 pm
Location: Comin' to you directly from the Mothership

Re: How recursive is the real world?

Mon Mar 27, 2017 2:53 pm

OK directory searches make sense, since you'd search each directory within each directory and there's no telling how deep it goes from an iteration standpoint. It'd be super weird to do with loops.

I'm not all that familiar with data structures, at least in part because we've just been using off-the-shelf databases like SQL 2014 at work. I've spent around 20 minutes reading this supplementary stuff on B-Trees. I'm sure there's a lot more to soak in, though.

Two helpful answers, though. Thanks to you both!

edit: Yes, I had infinite recursion in my first pass of the homework assignment, because I missed one of my base cases. :lol:
I do not understand what I do. For what I want to do I do not do, but what I hate I do.
 
just brew it!
Gold subscriber
Administrator
Posts: 50802
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Re: How recursive is the real world?

Mon Mar 27, 2017 2:58 pm

Oh, and BTW... just an amusing little Easter egg: If you Google "recursion", the results start with "Did you mean: recursion" :D
Nostalgia isn't what it used to be.
 
just brew it!
Gold subscriber
Administrator
Posts: 50802
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Re: How recursive is the real world?

Mon Mar 27, 2017 3:30 pm

Redocbew wrote:
There are some real oddballs(like the Ackermann function)

Egads, that is a weird one. Deceptively simple, but leads to some really bizarre (and unexpected) behavior for seemingly innocuous inputs. A(3,5) results in a maximum recursion depth of 254, and 42438 total invocations of A()!?!? :o

(Anything beyond that causes the Python interpreter to blow up due to excessive recursion depth...)
Nostalgia isn't what it used to be.
 
srg86
Gerbil Team Leader
Posts: 237
Joined: Tue Apr 25, 2006 7:57 am
Location: Madison, WI

Re: How recursive is the real world?

Mon Mar 27, 2017 3:54 pm

PCI/PCIe enumeration uses a recursive algorithm. I think walking page tables can also be, at least to a point.
Intel Core i7 4790K, Z97, 16GB RAM, 128GB m4 SSD, 480GB M500 SSD, 500GB WD Vel, Intel HD4600, Corsair HX650, Fedora x64.
Thinkpad T460p, Intel Core i5 6440HQ, 8GB RAM, 512GB SSD, Intel HD 530 IGP, Fedora x64, Win 10 x64.
 
derFunkenstein
Gold subscriber
Gerbil God
Topic Author
Posts: 24256
Joined: Fri Feb 21, 2003 9:13 pm
Location: Comin' to you directly from the Mothership

Re: How recursive is the real world?

Mon Mar 27, 2017 4:35 pm

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"
I do not understand what I do. For what I want to do I do not do, but what I hate I do.
 
Redocbew
Gold subscriber
Gerbil Jedi
Posts: 1548
Joined: Sat Mar 15, 2014 11:44 am

Re: How recursive is the real world?

Mon Mar 27, 2017 5:12 pm

Trees are often a good fit. It's really the branching of a tree structure which makes it work that way. Each node in a tree structure can be thought of as the root of its own tree.

A linear data structure, like a stack can be divided up this way also since it's basically just a tree with only one branch, but in that case you're doing a lot of extra work for something that can be traversed much more simply with a loop. If there's no implied hierarchy in the data, then that can help influence the decision also.
Do not meddle in the affairs of archers, for they are subtle and you won't hear them coming.
 
223 Fan
Gold subscriber
Gerbil
Posts: 58
Joined: Wed Jun 26, 2013 4:41 pm

Re: How recursive is the real world?

Mon Mar 27, 2017 5:14 pm

In functional programming tail call recursion is pretty important. Basically because tail call optimization ends up being a for loop instead of blowing through your stack.
 
Usacomp2k3
Gerbil God
Posts: 21945
Joined: Thu Apr 01, 2004 4:53 pm
Location: Orlando, FL
Contact:

Re: How recursive is the real world?

Mon Mar 27, 2017 6:42 pm

I've used it (or attempted to) in SQL for doing indented BOM's.
 
morphine
Gold subscriber
Gerbilus Supremus
Posts: 11453
Joined: Fri Dec 27, 2002 8:51 pm
Location: Portugal (that's next to Spain)

Re: How recursive is the real world?

Mon Mar 27, 2017 7:04 pm

Like others have pointed out, it's sprinkled across the "real world," just not as much as you'd think, for the reason that declarative code is easier to understand and (usually) not so easy to screw up. Having said that, let it be extremely clear that it's not "recursion sucks." It's more like "it's an extremely powerful tool that must be wisely used." For example, there are some bits of the front-page comment parser on this site that rely on recursion (nested quotes, lists, etc).

However, keep in mind "functional programming" languages like F#, Caml, and so on that treat every task like a recursion, and most of every "thing" as a list of whatever. The reason for that is that it's easy to think of everything like a mathematical function. Oversimplificating: to print a list of numbers in one of those languages, you tend to write a small function that will apply a function (print) to a list of numbers, by printing one then feeding itself the list of numbers minus the first one, and so on and so forth. Here's an example.

If you're still wondering "but why," the reason is that 1) you can write very small code that does a lot of things, 2) it's easier if not pretty much implicit that your code can't have side-effects, 3) for scientific tasks it's damn near perfect, and 4) academics love the associated math-function-mental-masturbation anyway. Yes, I said that, and if we're going to fight on that, cashmeousside, I'll go and get the gloves.
There is a fixed amount of intelligence on the planet, and the population keeps growing :(
 
Mr Bill
Gold subscriber
Gerbil Jedi
Posts: 1530
Joined: Mon Jan 21, 2002 7:00 pm
Location: Colorado Western Slope
Contact:

Re: How recursive is the real world?

Mon Mar 27, 2017 7:10 pm

I recall that recursive functions can be used to make realistic coastline, topography, clouds, trees, leaves, etc. because many phenomenon and shapes are self symmetrical at all levels of detail.
X6 1100T BE | Gigabyte GA-990FXA-UD3 AM3+ | XFX HD 7870 | 16 GB DDR3 | Samsung 830/850 Pro SSD's | Logitech cherry MX-brown G710+ | Logitech G303 Daedalus Apex mouse | SeaSonic SS-660XP 80+ Pt | BenQ 24' 1900x1200 IPS | APC Back-UPS NS-1350 | WinXP64 Pro
 
Redocbew
Gold subscriber
Gerbil Jedi
Posts: 1548
Joined: Sat Mar 15, 2014 11:44 am

Re: How recursive is the real world?

Mon Mar 27, 2017 7:22 pm

Yeah, fractals are another one of those oddball things which have a recursive definition.
Do not meddle in the affairs of archers, for they are subtle and you won't hear them coming.
 
DancinJack
Grand Gerbil Poohbah
Posts: 3550
Joined: Sat Nov 25, 2006 3:21 pm
Location: Kansas

Re: How recursive is the real world?

Mon Mar 27, 2017 7:44 pm

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 int bensFactorial (int x)
{
  if (x > 1)
  {
     //recursive case:
     return bensFactorial(x-1) * x;
  }

  else  /*base case*/
     return 1;

}
i7 6700K - Z170 - 16GiB DDR4 - GTX 1080 - 512GB SSD - 256GB SSD - 500GB SSD - 3TB HDD- 27" IPS G-sync - Win10 Pro x64 - Ubuntu/Mint x64 :: 2015 13" rMBP Sierra :: Canon EOS 80D/Sony RX100
 
SecretSquirrel
Minister of Gerbil Affairs
Posts: 2354
Joined: Tue Jan 01, 2002 7:00 pm
Location: North DFW suburb...
Contact:

Re: How recursive is the real world?

Mon Mar 27, 2017 7:55 pm

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;
}
 
superjawes
Gold subscriber
Gerbil Jedi
Posts: 1921
Joined: Thu May 28, 2009 9:49 am

Re: How recursive is the real world?

Mon Mar 27, 2017 10:32 pm

I don't mean to derail this topic, but I keep seeing the title, and I can't help but read it to the tune of "Keep on Rockin' in the Free World".

Anyways...carry on.
On second thought, let's not go to TechReport. Tis a silly place.
 
NovusBogus
Silver subscriber
Graphmaster Gerbil
Posts: 1255
Joined: Sun Jan 06, 2013 12:37 am

Re: How recursive is the real world?

Mon Mar 27, 2017 11:54 pm

Recursion is one of the few things covered in my academic classes that I've actually used as a professional developer.

A few examples that come to mind:

-Directory traversal for populating a file library
-Comparing two XML trees. This one is also the only time I can think of where I cared about big-O performance approximation, as the tree was rather large.
-File conversion utilities
-Propagating a change through a complex, multi-level financial database

Probably some others I can't recall as well. It's the usual way of dealing with arbitrary parent-child relationships, which are very common thanks to the proliferation of XML based data.
 
DragonDaddyBear
Gerbil Elite
Posts: 717
Joined: Fri Jan 30, 2009 8:01 am

Re: How recursive is the real world?

Tue Mar 28, 2017 7:15 am

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.

Get-ADGroupMember "GroupName" -Recursive
 
just brew it!
Gold subscriber
Administrator
Posts: 50802
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Re: How recursive is the real world?

Tue Mar 28, 2017 7:27 am

Losergamer04 wrote:
I do a lot of PowerShell. I won't even try to hold a candle to what you guys do.

Hey, don't sell yourself short. Advanced scripting tools like PowerShell (and its cousins on the *NIX side of the house like bash) qualify as programming languages in their own right, and you can do some pretty sophisticated stuff in situations where squeezing absolute best performance out of the system isn't a priority.

We've come a long way since MS-DOS .BAT files! :wink:
Nostalgia isn't what it used to be.
 
lycium
Gerbil Team Leader
Posts: 294
Joined: Fri Feb 03, 2006 8:18 pm
Location: wroclaw
Contact:

Re: How recursive is the real world?

Tue Mar 28, 2017 7:47 am

I develop a commercial fractal art application, Chaotica, and often get emails asking me how much psychedelic drugs I take... I've never actually tried any (unfortunately?), however to me it's very interesting that people ask all the time - there's clearly something about the human brain that sees fractals (the basis of which is recursion) in altered states.

Of course, one sees fractals very often in nature (trees, clouds, coastlines, ...), and a simple recursive cellular automaton even appears on some sea shells: https://en.wikipedia.org/wiki/Rule_30
 
derFunkenstein
Gold subscriber
Gerbil God
Topic Author
Posts: 24256
Joined: Fri Feb 21, 2003 9:13 pm
Location: Comin' to you directly from the Mothership

Re: How recursive is the real world?

Tue Mar 28, 2017 7:55 am

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)


We went about it a little differently. We were instructed to address base cases first and then do any calculations and finally call the function again. Not that he said it couldn't be done differently, just that dealing with the base cases first will help us keep the code organized.

    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);
    }


Although I guess either way works.

I have 6 little single-function projects like that for different things. Exponents, greatest common divisor (Euclidian algorithm), swapping pairs of elements in an array, counting vowels, and that even/odd thing where I missed a base case early on. So it'll become automatic over time, I'm sure. :lol:
I do not understand what I do. For what I want to do I do not do, but what I hate I do.
 
lycium
Gerbil Team Leader
Posts: 294
Joined: Fri Feb 03, 2006 8:18 pm
Location: wroclaw
Contact:

Re: How recursive is the real world?

Tue Mar 28, 2017 7:58 am

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). For example if you swap out the GPU and the problem persists, you've probably ruled out a whole class of possible problems (GPU overheating, GPU running out of memory from lots of Chrome tabs, GPU dying of old age, problematic GPU drivers, ...).

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).
Last edited by lycium on Tue Mar 28, 2017 8:03 am, edited 1 time in total.
 
derFunkenstein
Gold subscriber
Gerbil God
Topic Author
Posts: 24256
Joined: Fri Feb 21, 2003 9:13 pm
Location: Comin' to you directly from the Mothership

Re: How recursive is the real world?

Tue Mar 28, 2017 8:02 am

Hey that's a great example. Subdividing a problem into more manageable pieces—divide and conquer—is how my brain has always worked (and I think that's true for just about everyone who is technically inclined).

And I don't want to gloss over everything that folks have said about recursion in nature. I never really thought about it, but symmetry is everywhere.
I do not understand what I do. For what I want to do I do not do, but what I hate I do.
 
just brew it!
Gold subscriber
Administrator
Posts: 50802
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Re: How recursive is the real world?

Tue Mar 28, 2017 8:13 am

It isn't really about symmetry, it is more about self-similarity (looking essentially the same at different levels of detail).
Nostalgia isn't what it used to be.
 
derFunkenstein
Gold subscriber
Gerbil God
Topic Author
Posts: 24256
Joined: Fri Feb 21, 2003 9:13 pm
Location: Comin' to you directly from the Mothership

Re: How recursive is the real world?

Tue Mar 28, 2017 8:13 am

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.

Get-ADGroupMember "GroupName" -Recursive

I'm 38 years old and just now learning this stuff. I don't know how old you are, but I will say it's very unlikely you're unable to learn later in life. If you're interested in it and have some free time, there are free resources to introduce you to just about any language you want. When I first started thinking about all this, I chose C# and Windows Phone 8. That second course didn't turn out to be all that useful, though that wasn't the instructor's fault. :lol:
I do not understand what I do. For what I want to do I do not do, but what I hate I do.
 
SecretSquirrel
Minister of Gerbil Affairs
Posts: 2354
Joined: Tue Jan 01, 2002 7:00 pm
Location: North DFW suburb...
Contact:

Re: How recursive is the real world?

Tue Mar 28, 2017 8:15 am

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).


This is actually a good example. When given a huge problem space (the computer isn't working right), you test a potential solution and based on it's outcome you may remove a large set of potential problems from consideration. You prune an entire branch off the search tree. You then traverse down some branch of the remaining tree and start testing other solutions and (hopefully) removing other large branches off the solution tree. Eventually, you get down to some tests/fixes that are very specific and don't really tell you much about other potential solutions. They either fix the problem or they don't. These are the leaves of the tree. If you find one that solves your problem, you are done. If not then you go back up the tree to a point at which you have other solution spaces to try -- you take another branch somewhere in the tree.

Now, here is the key. Not everyone approaches problem solving that way. I'm not talking about having experience and intuition that gets you to the right solution space quicker than just working your way logically through a decision/debugging tree. I'm talking about the difference between people who inherently approach all problems this way and people who just seem to try random unrelated solutions in a scatter-shot manner. So don't feel bad if you don't get trees and recursion, you may just not think that way. Like so many other skills, most people can be taught to approach a problem in such a manner, but you can always tell the people who inherently think that way. It's just "easy" for them. Just like those for whom music comes naturally.

--SS
 
lycium
Gerbil Team Leader
Posts: 294
Joined: Fri Feb 03, 2006 8:18 pm
Location: wroclaw
Contact:

Re: How recursive is the real world?

Tue Mar 28, 2017 8:15 am

JBI right on the money :) 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).

While I've got people's attention, I'd like to mention two of the most beautiful algorithms I know, the latter of which is obscenely recursive!

https://en.wikipedia.org/wiki/Barnes%E2 ... simulation (For large gravitational simulation)
https://en.wikipedia.org/wiki/Hashlife (For very efficiently implementing Conway's Game of Life)

Who is online

Users browsing this forum: No registered users and 1 guest