Personal computing discussed

Moderators: renee, SecretSquirrel, just brew it!

 
SuperSpy
Minister of Gerbil Affairs
Posts: 2403
Joined: Thu Sep 12, 2002 9:34 pm
Location: TR Forums

Re: How recursive is the real world?

Tue Mar 28, 2017 8:22 am

just brew it! wrote:
We've come a long way since MS-DOS .BAT files! :wink:


Some of us are still stuck in that world :evil:
Desktop: i7-4790K @4.8 GHz | 32 GB | EVGA Gefore 1060 | Windows 10 x64
Laptop: MacBook Pro 2017 2.9GHz | 16 GB | Radeon Pro 560
 
notfred
Maximum Gerbil
Posts: 4610
Joined: Tue Aug 10, 2004 10:10 am
Location: Ottawa, Canada

Re: How recursive is the real world?

Tue Mar 28, 2017 9:23 am

I've used recursion in walking paths across networks for diagnostics. You may have tunnels and you need to know which nodes the path traverses, including all the nodes the tunnels traverse.

I've also seen recursion bite badly, it led to a stack smash that caused a 10G line card to reboot while running live traffic between two cities.
 
Redocbew
Minister of Gerbil Affairs
Posts: 2495
Joined: Sat Mar 15, 2014 11:44 am

Re: How recursive is the real world?

Tue Mar 28, 2017 5:56 pm

derFunkenstein wrote:
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.
...
So it'll become automatic over time, I'm sure. :lol:


Yeah, it does. Recursion helps to give you an appreciation for the complexity of certain problems even if you don't use it much. Once you learn it, recursion makes everything easier. :P

Making the recursive call at the end of the function is called tail recursion, which 223 Fan mentioned earlier. Being able to use tail recursion usually means an iterative solution wouldn't be too difficult, but it does help to keep things simple. There are some cases, like in an XML parser which has to walk the document tree and perform some computation on each node afterwards where tail recursion may not be suitable, and that's when things can start to get interesting.
Do not meddle in the affairs of archers, for they are subtle and you won't hear them coming.
 
SecretSquirrel
Minister of Gerbil Affairs
Posts: 2726
Joined: Tue Jan 01, 2002 7:00 pm
Location: North DFW suburb...
Contact:

Re: How recursive is the real world?

Tue Mar 28, 2017 6:20 pm

notfred wrote:
I've used recursion in walking paths across networks for diagnostics. You may have tunnels and you need to know which nodes the path traverses, including all the nodes the tunnels traverse.

I've also seen recursion bite badly, it led to a stack smash that caused a 10G line card to reboot while running live traffic between two cities.


This is a very important point. If the problem space doesn't inherently limit the depth of recursion, the algo must have an exit case that prevents the recursion from getting too deep.

--SS
 
Mr Bill
Gerbil Jedi
Posts: 1819
Joined: Mon Jan 21, 2002 7:00 pm
Location: Colorado Western Slope
Contact:

Re: How recursive is the real world?

Tue Mar 28, 2017 6:30 pm

lycium wrote:
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
In the far far ago, TR used to use the mandelbrot set as a benchmark.
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 | Win7 Pro
 
just brew it!
Administrator
Posts: 54500
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Re: How recursive is the real world?

Tue Mar 28, 2017 6:33 pm

FWIW, although the Mandelbrot set has the self-similarity at multiple scales typical of fractals, the usual method for calculating it is iterative, not recursive.

Edit: Obligatory Mandelbrot fractal "deep zooms" (raw frames originally rendered on my FX-8350 desktop, using a custom Python/C program):
http://uchima.net/fractal-videos/mbzoom16.mp4
http://uchima.net/fractal-videos/mbzoom22.mp4
Nostalgia isn't what it used to be.
 
morphine
TR Staff
Posts: 11600
Joined: Fri Dec 27, 2002 8:51 pm
Location: Portugal (that's next to Spain)

Re: How recursive is the real world?

Tue Mar 28, 2017 9:24 pm

SecretSquirrel wrote:
This is a very important point. If the problem space doesn't inherently limit the depth of recursion, the algo must have an exit case that prevents the recursion from getting too deep. --SS


if ( dives > 100000 )
    return ERR_we_dun_effed_up;
There is a fixed amount of intelligence on the planet, and the population keeps growing :(
 
Captain Ned
Global Moderator
Posts: 28704
Joined: Wed Jan 16, 2002 7:00 pm
Location: Vermont, USA

Re: How recursive is the real world?

Tue Mar 28, 2017 9:31 pm

morphine wrote:
if ( dives > 100000 )
    return ERR_we_dun_effed_up;

Eddie could have used that when faced with the Tea Question.
What we have today is way too much pluribus and not enough unum.
 
derFunkenstein
Gerbil God
Topic Author
Posts: 25427
Joined: Fri Feb 21, 2003 9:13 pm
Location: Comin' to you directly from the Mothership

Re: How recursive is the real world?

Mon Jun 12, 2017 7:49 am

OK, so I just used recursion in the real world.

The QA instances of the web app that my mobile project goes with get rebuilt every morning and maybe a couple times throughout the day. If the mobile app is the first app to access those instances, they have to spin up. The web client tier deals with this by displaying a "loading" message and refreshing the page every second until it gets a valid response. Up until today, the Xamarin Forms re-write (hooray for dumping obscure platforms!) would just display a blank login page and no indication that anything was loading.

So I figured out that if one of the mandatory fields is empty, I could sleep for five seconds and retry, until a total of 30 seconds has passed like so. This isn't rocket science, and I'm sure you seasoned vets will laugh because this is a simple problem, but I'm really quite happy to use something from a class that seemed abstract in a real way.

public async Task<LoginSettings> GetLoginSettings(retries = 0)
{
   var loginSettings = new LoginSettings();

   if (retries <= 5)
   {
      loginSettings = DoSomething();
      if (string.IsNullOrEmpty(loginSettings.someRequiredField))
      {
         await Task.Delay(5000);
         return await GetLoginSettings(retries + 1);
      }
   }   

   return loginSettings;
}
I do not understand what I do. For what I want to do I do not do, but what I hate I do.
Twittering away the day at @TVsBen
 
Flying Fox
Gerbil God
Posts: 25690
Joined: Mon May 24, 2004 2:19 am
Contact:

Re: How recursive is the real world?

Mon Jun 12, 2017 2:22 pm

You are just doing retries. Could have just rewrite this without the "recusive" call. You are already doing the async pattern which can be tricky to begin with (no CancellationToken?). Besides, your DoSomething is sync, I am not sure why you want to make this async.

Ninja: what's your error condition if retries are exhausted? A "blank" object? Perhaps null would be better? Or an exception?
The Model M is not for the faint of heart. You either like them or hate them.

Gerbils unite! Fold for UnitedGerbilNation, team 2630.
 
Mr Bill
Gerbil Jedi
Posts: 1819
Joined: Mon Jan 21, 2002 7:00 pm
Location: Colorado Western Slope
Contact:

Re: How recursive is the real world?

Mon Jun 12, 2017 3:34 pm

lycium wrote:
Speaking in even greater generality, most people employ a recursive algorithm in general problem solving: "divide and conquer"....
Quicksort comes to mind.
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 | Win7 Pro
 
derFunkenstein
Gerbil God
Topic Author
Posts: 25427
Joined: Fri Feb 21, 2003 9:13 pm
Location: Comin' to you directly from the Mothership

Re: How recursive is the real world?

Mon Jun 12, 2017 10:33 pm

Flying Fox wrote:
You are just doing retries. Could have just rewrite this without the "recusive" call. You are already doing the async pattern which can be tricky to begin with (no CancellationToken?). Besides, your DoSomething is sync, I am not sure why you want to make this async.

Ninja: what's your error condition if retries are exhausted? A "blank" object? Perhaps null would be better? Or an exception?

Error is handled in the ViewModel when the "blank" object is returned. Give the user an error that the server isn't responding and redirect them to the instance lookup page, because closing out entirely when a server may have just moved seemed kinda rude.

if (loginSettings == null)
{
   await CrapYourPantsInAGracefulWay();
}


Also there's about 6 lines of code represented by DoSomething from initializing a WebRequest to retrieving it to deserializing a JSON object. It wasn't the point of my example, so I just put a placeholder. It's all running asynchronously, don't worry. :p

You can do a lot of stuff without recursion. This could have been in a do (while) loop but I spotted a use for something that didn't seem like too big of a stretch so I used it. I don't expect anybody here to be impressed with my coding skillz. :lol:
I do not understand what I do. For what I want to do I do not do, but what I hate I do.
Twittering away the day at @TVsBen
 
Redocbew
Minister of Gerbil Affairs
Posts: 2495
Joined: Sat Mar 15, 2014 11:44 am

Re: How recursive is the real world?

Mon Jun 12, 2017 10:47 pm

I approve of any attempt for code to crap its pants gracefully. There's an alarming amount of code out there which is simply incontinent by comparison. :P
Do not meddle in the affairs of archers, for they are subtle and you won't hear them coming.
 
notfred
Maximum Gerbil
Posts: 4610
Joined: Tue Aug 10, 2004 10:10 am
Location: Ottawa, Canada

Re: How recursive is the real world?

Tue Jun 13, 2017 8:30 am

The do while loop would avoid chewing up stack space and be faster as it doesn't have the function call overhead on each loop.

Who is online

Users browsing this forum: No registered users and 1 guest
GZIP: On