Darren's Weekly Nugget 01/04/2010

[Darren]

Many LabVIEW users were excited to find out that native recursion support was added to LabVIEW 2009.  This basically means that, after tweaking some reentrancy settings, a VI can call itself recursively during execution.  This feature has been highly requested over the years.  Although recursion was always possible with VI Server, it was never as easy as dropping a VI on its own diagram, which you can now do in LabVIEW 2009.

I must admit, though, that I never particularly felt the need to have this feature, and so far, I haven't used it.  Prior to the LabVIEW 2009 release, I heard complaints from many developers over the years (almost all of whom got their start in text-based programming) about how LabVIEW didn't have support for native VI recursion.  The first time I heard that complaint, my response was, "Anything that you think you need recursion for, I bet I can do with a While Loop and a shift register".  That was probably an overly simplistic response on my part, but to be honest, it's pretty much always been true.

Take the Recursive File List VI as an example.  I shipped this VI in LabVIEW 7.0, and finally got around to adding it to the palettes in LabVIEW 8.2.  If you look at this VI's diagram, you'll see that at its core, I'm using a simple scheme to recurse all the subdirectories to get a listing of all the files.  I've seen other developers attempt to solve this problem before with recursive calls, and their implementations are usually orders of magnitude slower than mine.  The simple explanation is probably that the overhead of building up the path array is much smaller than the overhead of keeping all those VI instances in memory.  I will admit, though, that I haven't seen a performance comparison since native recursion was added in LabVIEW 2009...I'd be interested to see the results of that benchmarking.

I guess it probably comes down to what approach the developer is comfortable with.  Since I was never a text-based programmer, While Loops and shift registers come very naturally to me, and the idea of a VI calling itself is rather foreign.  The opposite is probably true for a text-based programmer, who is probably familiar and comfortable with having a function call itself.

I guess the gist of this nugget is that, if you feel uncomfortable with the idea of a VI sitting on its own diagram, don't feel bad...I think it's weird, too.  😉

[Darin.K]

I don't remember who said it, but I was told during one of my CS classes that "To understand recursion you must first understand recursion".

I was certainly one of those who was very glad to see native recursion supported in LV.  Even so, this was almost entirely for fun by which I mean theoretical interest.  I have yet to have many practical uses for it myself.  A few points off the top of my head.

If you mention "benchmarking" and recursion in the same sentence you are in trouble.  Recursion is almost always an inefficient way to solve a problem, the Fibonacci example is one of the worst offenders in this regard.

Re: while loop and shift register.  Most looping constructs exist because compilers have trouble dealing with recursion.  The problem stems from the fact that you have to store the "state" of your program each time you make a recursive call.  When the compiler does this, it usually ends up storing a lot of extra information.  When you use a shift register, you have control over what information needs to be carried over from one iteration to the next. 

The beauty of recursion (purposely subjective) is that your algorithm appears very simple and very close to the mathematical definition.  If you have a problem that you only need to solve once, it can be reassuring that your algorithm is very straightforward.

Finally, as your recursive file search demonstrates, there is a fundamental difference between a recursive function and a recursive implementation.

In short, thanks to whoever is responsible for implementing native recursion, it really made my day.  I'll invert your statement and say anything that you can do with a while loop I can do with recursion, I just won't be racing any time soon.

[tst]

---

Darren wrote:

...my response was, "Anything that you think you need recursion for, I bet I can do with a While Loop and a shift register".  That was probably an overly simplistic response on my part, but to be honest, it's pretty much always been true.

---

Luckily, you're not in school anymore, so no one is asking you to prove it 😉 . If it makes you feel better, it's a classic argument, and there are proofs showing that any recursive algorithm can also be implemented using a stack.

[F._Schubert]

Recursion is really great when we deal with recursive structures (lists, trees), the file list being a good example. Other scenarios ar xml-data, parse trees (mathematical functions, compilers). In OOP, there are nice patterns that work good with recursion (Visitor).

Using a while loop with shift registers always mades my head hurt. I prefer the recursion with the VI server over this, although it is really slow. And there is a lot of design overhead (all the type casting to the ConPane must be done each time you change the ConPane). What takes a lot of space (Open VI Reference, strict VI Refnum, Call VI, Close VI Reference and Merge Errors) is now reduced to the simple VI. Nice...

Felix 

[jcarmody]

---

Darin.K wrote:

I don't remember who said it, but I was told during one of my CS classes that "To understand recursion you must first understand recursion".

---

Google recursion, it's almost as clever.

[Ben]

---

Darren wrote:

... my response was, "Anything that you think you need recursion for, I bet I can do with a While Loop and a shift register".  That was probably an overly simplistic response on my part, but to be honest, it's pretty much always been true.

...

I guess the gist of this nugget is that, if you feel uncomfortable with the idea of a VI sitting on its own diagram, don't feel bad...I think it's weird, too.  😉

---

Interesting ideas...

I used recurcion in my Save/Restore using control refs Nugget.

That code can handle arbitrary data structures and the recursion let my code adapt to the data at run time.

Do you think you could have done that with SR's?

For the most part I don't use recursion unless the problem screams for it (like above). I think this may come from how I think about coding. I will almost always "write the code in my head" before dropping any operators and recurcion is "just so damn hard to see".

Ben

Message Edited by Ben on 01-05-2010 08:21 AM

[Hooovahh]

Yesterday was the first time that I ever used recursion native or not.  It was in a case that I knew I could use a while loop instead, but I wanted to try the new feature (new meaning native now of course).  It worked like it should, and I only once had an infinite loop that I had to create a fix for.

I doubt I'll use recursion much but it's nice to know it's there.

[J.DECHET]

One more step to the wireless LabVIEW

[Intaris]

@Ben,

I've done a reference-based adaptive system just like yours and I used Shift registers.

I have written a SR version of the software before I've managed to get my head around the Recusrion idea.....

Shane.

[JÞB]

Recursion

Can be fairly useful.