Data only recursion vs data&function(object) recursion

[Jacemdom]

Salut.

In relation to : Automatic Recursion, Recursive Brat

I don't see any advantages of implementing recursion with recursive functions instead of just recursing trough with a recursive data structure. Can someone give some?

[LAVA 1.0 Content]

I don't see any advantages of implementing recursion with recursive functions instead of just recursing trough with a recursive data structure. Can someone give some?

Think of a company organization. CEO of the organization gives the vice presidents a task to take care of something. CEO is a busy man, he doesn't know how do the VPs deal with the issue, he just knows that the VPs get it done. The VPs may do it by them selves or they may delegate the issue further. The task may be delegated many many times to number of people and each one takes care of a small task.

In object oriented programming data driven recursion is hard to implement as you do not know in the root class what kind of properties do the other classes in the hierarchy have. You can think the root class to be like the CEO of the company. The root class can only start the recursion but doesn't know any special issues it has to do with the recursion. It's the class methods further down the hierarchy that really know all special issues about the recursion. Even though recursion may perhaps be implemented in this case also using data driven recursion and intelligent class design, it is much easier to implement using direct function calls to appropriate methods. It is easy for the CEO to delegate almost any task to the VPs but it's hard to define a process that works for every possible task in the company troughout the whole company hierarchy. Still it's not very complicated to implement an abritrary process if people in the organization just delegate parts of the task further if they cannot do it.

You can think of an organization consisting of LabVIEW objects. You have a CEO class, a VP class, a senior manager class, a junior manager class and a number of different kinds of expert classes such as a LabVIEW nerd class. Each employee object belongs to one of these classes. The CEO class has a method delegate and the CEO class knows the who are the VPs. That's all the CEO class knows about the organization, after all CEOs are busy doing PR on the field with other CEOs. So from this point of view, how can you model a task penetration in the organization as you only know what the CEO can do. In order to be able to mode the task penetration you would have to know the capabilities of all the different employee classes. Well, you can do it, you'll need a case structure for all your class types in a while loop but you could do it. But then when your company decides to hire lawers and consultants, you need to modify all your recursion loops. If you were doing recursion trough functions, you only need to implement these new classes and define the connections to other classes. This is something you need to do anyhow, but you save the work of rewriting all your recursion every time your class structure changes.

[Jacemdom]

Think of a company organization. CEO of the organization gives the vice presidents a task to take care of something. CEO is a busy man, he doesn't know how do the VPs deal with the issue, he just knows that the VPs get it done. The VPs may do it by them selves or they may delegate the issue further. The task may be delegated many many times to number of people and each one takes care of a small task.

In object oriented programming data driven recursion is hard to implement as you do not know in the root class...

Some clarifications of my quest...

I am looking for already solved or to be solved with software in real life cases in order to analyse why the native dataflow in LabVIEW could not solve efficiently a particular case in order to comprehend why it is needed to push recursion as well on the methods side. I would like to see what are the limits of the dataflow if there are any on this subject. One clear limit with the dataflow being sharing data between parallel process, i would like to analyse recursion in the same way.

So here is the first case for analysis.

Recursion case 1 :

Listing the content of a folder. And all subfolders...and all subfolders and... i see no need or advantages to push the recursion on the methods(VIs) also.

[Aristos Queue]

Recursion case 1 :

Listing the content of a folder. And all subfolders...and all subfolders and... i see no need or advantages to push the recursion on the methods(VIs) also.

The classic would be calculating Fibbonacci numbers:

F(0) = 1

F(1) = 1

F(n) = F(n-1) + F(n-2)

Coming up with a data structure to do this recursion is annoying, especially when the the function definition is already known.

[Jacemdom]

The classic would be calculating Fibbonacci numbers:

F(0) = 1

F(1) = 1

F(n) = F(n-1) + F(n-2)

Coming up with a data structure to do this recursion is annoying, especially when the the function definition is already known.

Have you ever had to use this in a concrete (deployed solution working and used by someone else) solution? If yes, could you explain the problem so that i can put it in perspective?

Would your expression equal this in LV? If yes, what would function recursion add?

The top one is the simpler believed to equal your expression and the below one is a configurable one where n can be changed to make somthing like

F(0) = 1

F(1) = 1

F(x) = 1

F(n) = F(n-1) + F(n-2) + F(n-x)...

[Aristos Queue]

Have you ever had to use this in a concrete (deployed solution working and used by someone else) solution? If yes, could you explain the problem so that i can put it in perspective?

Used by someone else? Except for LV, none of my code gets used by someone else generally. But I have used it in graphics applications (specifically screen saver apps) that others could've written. The Fibonacci sequence underlies the golden ratio that is so useful for layout and design.

Whether or not I have used that particular math expression is beside the point... I've actually had many math expressions of the form "F(x) = F(g(x)) with some recursive base case" over the years that have been in deployed code. Newtonian approximation of functions comes to mind.

As for the code, what does function recursion add? Readability. Your VI works... I think. It took me 20 minutes of staring to figure out what the heck a divide operation had to do with calculating this value. Compare with this:

[Mads]

Quicksort is an example of a function that is naturally made by using recursion...however it is too slow in LV so it is faster (but less elegant) to do it without recursive calls.

I needed recursion for the development of this code:

http://zone.ni.com/devzone/cda/epd/p/id/12

Mads

Have you ever had to use this in a concrete (deployed solution working and used by someone else) solution? If yes, could you explain the problem so that i can put it in perspective?

Would your expression equal this in LV? If yes, what would function recursion add?

The top one is the simpler believed to equal your expression and the below one is a configurable one where n can be changed to make somthing like

F(0) = 1

F(1) = 1

F(x) = 1

F(n) = F(n-1) + F(n-2) + F(n-x)...

[robijn]

As for the code, what does function recursion add? Readability. Your VI works... I think. It took me 20 minutes of staring to figure out what the heck a divide operation had to do with calculating this value.

Yeah. What about a VI option "instantiate on call", creating a dataspace when it is called.

Would behave just like the combo {Open VI ref reentrant, call VI, close ref} currently does.

Could be nice for objects too (no matter whether the wire is containing or referencing)

Joris

[Jacemdom]

As for the code, what does function recursion add? Readability. Your VI works... I think. It took me 20 minutes of staring to figure out what the heck a divide operation had to do with calculating this value. Compare with this:

For an equal comparison, your code must be compared to the top example, that does not involve a division, and not the bottom one that permits higher orders of recursions.

So it is this one :

That i find even simpler due to the fact that it does not hide code in a case structure.

[Aristos Queue]

Believe it or not, I really don't want to argue implementations... you asked for examples of recursion, I tried to provide one. I gave a simple case as an exemplifier of an entire class of problems.

For an equal comparison, your code must be compared to the top example, that does not involve a division, and not the bottom one that permits higher orders of recursions.

So it is this one :

That i find even simpler due to the fact that it does not hide code in a case structure.

Your version, although I conceed it is simpler, does not match the function defintion... if I'm trying to confirm that your code matches the specification of the function, my first question is "Where are the two 'minus one' calls?" The fact that you found a way to provide the value without ever having the -1 calculation means that you had to think about how to encode the function in a VI and get the same mathematical result, as opposed to simply encoding the function as specified. My general case remains. Instead of Fibbonacci, let's try Ackerman:

http://en.wikipedia.org/wiki/Ackermann_function

<img src="http://upload.wikimedia.org/math/0/a/e/0ae4053de098cc9554752b190a38bc56.png">

If you want to write a program to print out the table of values for the Ackerman function, you can do it without recursion (all recursive functions can be expressed iteratively) but you'll be hard pressed to show (other than by empirical printing of the table) that you'd gotten it right.

I went through a bunch of LV's C++ code and LV examples to find other recursion examples...

In LV C++ code, we use recursion for assigning depth indicies to a cluster in LV (here's pseudocode):

AssignToClust(cluster, int32 *curdepth) {	for (i = 0; i < number_of_elts_in_cluster; ++i) {		cluster[i] = *curdepth;		*curdepth += 1;		if (cluster[i] is a subcluster)			 AssignToClust(cluster[i], curdepth);	}

You know the int16 arrays that come out of the Flatten Variant primitive? Those are type descriptors. In the C++ code, we use a lot of recursion for traversing those (for actions such as "typedef changed names, find all embedded type descriptors and change the name").

Related to the previous example: Generation of XML for LabVIEW data is a series of recursive calls between multiple functions, not just a single function. ClusterToXML might call ArrayToXML might call ClusterToXML might call ArrayToXML might call I32ToXML. Each adds a header before calling the nested recursion function and then adds a tail after the nested function returns. Doing this with a stack implementation would be very non-trivial.

The routine to search LV palettes for a particular function is recursive: check this palette, if not found, check subpalettes sequentially. Believe it or not, we do this every time you right click on a node so that we can show you the source palette for the node. It continues to amaze me just how many calculations can be squeezed into the time between right-click and the appearance of the popup menu.

Here's an example that ships with LV that uses a stack implementation but would be simpler if we had recursion:

c:\program files\national instruments\LabVIEW 6.1\examples\general\queue.llb\Queue Stack - Solve Maze.vi

Downloading VIs to RT targets -- download top-level VI. The download each subVI (repeat recursively). This one is easy to have implemented with a queue of VIs -- enqueue the top level VI, then repeat "dequeue one VI, enqueue all its subVIs, download that VI to target" until the queue is empty. The hard ones are the ones where you need results from multiple recursions to take the next step. Like this next one...

Math string parsing: Given arbitrary string of numbers and the four basic math operations, evaluate the value of the expression. For example (1+3)*3-4/4)

Generally the Evaluate function is "search left to right to find the first * or /. Split the string and Evaluate each half and either * or / the results. If no * or / is found, do same for + or -. If not found, return the value of the string." Adding parentheses makes this a bit trickier, but you get the idea.

Game theory: pruning a game tree involves recursive evaluation of future states of the game "On turn n you can take possible moves 1 through m. G(n,m) is a good position if you have won the game or if the majority of possible G(n+1, [1..m]) moves are good positions..." Evaluate G(1, [1..m]) to decide the best first move."

[Jacemdom]

the subject of this thread could be "Stacked data vs function recursion implementations"

Your version, although I conceed it is simpler, does not match the function defintion...

I believe this implementation is more inline with your example and it looks more like your recursive implementation without the recursing function...

I know that recursion is used in other languages and that it is very popular with "professionnal programmers", but this is not what i'm looking for. I also know that recursion is used in LV and i would like to get some of those so i can code them with data only (iterative) coding and analyse the advantages and disadvantages of both implementation. This desire comes from a feeling that recursion is a shortcut in development and that it can lead to more bug prone software.

Related to the previous example: Generation of XML for LabVIEW data is a series of recursive calls between multiple functions, not just a single function. ClusterToXML might call ArrayToXML might call ClusterToXML might call ArrayToXML might call I32ToXML. Each adds a header before calling the nested recursion function and then adds a tail after the nested function returns. Doing this with a stack implementation would be very non-trivial.

I remember a comment a while ago on Info-LV (85% certainty that it came from Rolf.K.) stating that it can be harder to implement recursion with stacked algorithms, but it forces one to think of use cases that would not be considered when building the recursive function algorithm, and thus created more robust code. I also believe that recursion is highly popular in text languages as i don't beleive they offer already built looping with shift registers like LV does. And loops with shift registers are practically always the base for iterative data looping "recursive" algorithm.

If i try to use an analogy to convey my inner feeling about the subject (take into account that an analogy is not made to prove a point, but to give another point of view to share ones taughts)

Using function recursion in LV feels to me like someone using a hammer gun like an hammer and slamming the hammer gun on the nails...i also feel this way about OO in LV...old methods used in a new way of solving problems...

[bsvingen]

There are some things here that just cant be standing uncorrected

First: F(0) = 0 , not 1

Jace, your procedure in your last post does not calculate the fibonacci numbers, just try with the number 4 as input.

While recursion can be simple to implement (considering the language support it), it can be incredible slow if implemented naively on a non-optimizing compiler. For instance, a naive recursive implementation of the fibonacci number scales as O(2^n) while a iterative procedure scales with O(n). This means that to calculate F(32) requires approximately 32 operations when implemented iteratively and 4294967296 operations when implemented recursively. Even when implemented recursively and optimized it will take at least 1024 operations (scales as O(n^2)). See wikipedia for more.

For other things like trees, that do not have this terrible scaling problems, then i do not see why recursion should be simpler than using shift registers. When the procedure is of order O(N), this means that the function can be used as is, also in an iterative procedure.

[Jacemdom]

There are some things here that just cant be standing uncorrected

First: F(0) = 0 , not 1

Jace, your procedure in your last post does not calculate the fibonacci numbers, just try with the number 4 as input.

While recursion can be simple to implement (considering the language support it), it can be incredible slow if implemented naively on a non-optimizing compiler. For instance, a naive recursive implementation of the fibonacci number scales as O(2^n) while a iterative procedure scales with O(n). This means that to calculate F(32) requires approximately 32 operations when implemented iteratively and 4294967296 operations when implemented recursively. Even when implemented recursively and optimized it will take at least 1024 operations (scales as O(n^2)). See wikipedia for more.

For other things like trees, that do not have this terrible scaling problems, then i do not see why recursion should be simpler than using shift registers. When the procedure is of order O(N), this means that the function can be used as is, also in an iterative procedure.

Could this be simplified by saying : You don't see any advantages of using recursion vs stacked iterative implementation, and there could even be disadvantages?

I never heard of the Fibonnacci numbers before this topic...i am more interested at the recursion and stacked iterative implementation concepts regarding specifically LV.

[bsvingen]

I dont have labview on this computer, but the fibonacci number is very easy to implement iteratively in labview. Here is a C version from wikipedia

unsigned fib(unsigned n) {  int first = 0, second = 1;  // this while loop will exit when the int reaches 0  // it is equivalent to while(n != 0) { n-- .... }  while (n--)	{	  unsigned tmp = first+second;	  first = second;	  second = tmp;	}  return first;}

Just make a while loop with three shift registers, one to hold first, one to hold second and one to hold n (well, just make a LV version of the C code).

Fibonacci numbers are the typical example of recursion because they are always written recursively. But to implement a "standard library fibonacci routine" with recursion is complete insanity because the iterative version is so much more effective. F(100) would probably take years (seriously and literaly) to calculate recursively on a PC (coded in C), while it takes some nano seconds iteratively.

When the recursive routine is simply a straight linear iteration written recursively, then there are no difference in efficiency because both routines scale as O(N) (under the assumption that the cost of the recursive call itself is zero), and therefore a recursive routine will become more compact and "to the point". In LV the cost of a recursive call is far from zero, and the only extra thing needed compared with a recursive version, is an extra shift register in the loop.

[Aristos Queue]

Jacedom:

Using function recursion in LV feels to me like someone using a hammer gun like an hammer and slamming the hammer gun on the nails...i also feel this way about OO in LV...old methods used in a new way of solving problems...

Were any of the other situations that I posted "interesting cases" for you?

I want to keep pushing this discussion because your position is somewhat unique. 99% of the time, the question asked of LV R&D is not "Should LV have recursion?" The question usually asked is "why doesn't LV have recursion?" It gets asked with high frequency, and attempted by some developer on the team about once every two to three years as far as I can tell. This keeps the research focus on the question of how to do it. The LV R&D team has been pounding on the recursion problem for *years* (bordering on *decades*) and we've recently started making some headway for dataflow-safe recursion. This is definitely the time to be asking the "should" question. Statistical outlier opinions are always worth at least a glance -- the definition of genius is the guy who saw something obvious that everyone else missed.

Your basic position, as I understand it, is two-fold:

1) The overhead of recursion outweighs the ease of its coding.

2) The iterative solutions are possible (that's provable) and they're sufficiently easy to implement in LV as compared to other languages that they should be preferred.

Is that somewhat correct?

On the topic of overhead, the current "recursive" solution is VI Server with reentrant VIs. That's not recursion IMHO and of course its performance sucks. Recursion works, and works well, when it has what LabVIEW doesn't have: a call stack. The $64000 question is "can you build a dataflow safe call stack" or something that performs as well. If we (R&D) can do so, should we?

That brings us to the preference for iterative solutions. I want to debunk one comment about other languages not having shift registers... in this loop:

int i = 1;

while (true) {

++i;

}

'i' has the same functionality as a shift register. I've done a bit of work on a text-based version of LV using C syntax, and a shift register is nothing more than a variable you declare outside the loop and promise to only assign once at some point during the loop.

Is there some aspect of LV that you think dramatically improves a programmer's chances of correctly coding the iterative solution to most recursion functions as compared to the recursive solution? I don't know of anything myself, but I'm open to argument.

> I never heard of the Fibonnacci numbers before this

> topic...i am more interested at the recursion and

> stacked iterative implementation concepts regarding

> specifically LV.

I think the point is made that you tried to convert the formulas as written into an iterative solution and got it wrong. I'm not trying to rub this in, just pointing out that I myself find converting a recursive problem into an iterative solution VERY HARD. I think that most software engineers would botch conversion of all but the most trivial problems. As far as the comment about an iterative solution making you think about other use cases, I don't get that point at all. When I conceive the use cases for any function -- XML parser or whatever -- I do it independent of the implementation of the code. I don't see how looking for an iterative solution changes the functionality you're trying to provide.

I know that none of my arguments speak to the efficiency of code --- code performance frequently is better with an iterative solution than with a recursive solution. I've seen that. But in my 16 years of programming, I've learned the hard way that code correctness has to be the first priority and optimizing the code comes second, if it turns out to be needed at all.

LV doesn't have recursion today. But it continues to suck up R&D time because the demand for it is high. It turns out to be a hard problem to solve, but I assume that some decade it will be solved. I don't think you've convinced me yet that I ought to encourage my co-workers to turn their attention to something else.

[Chris Davis]

I've done a bit of work on a text-based version of LV using C syntax

Sorry to hijack the thread for a moment, but was this work related to LV Embedded, or some other project?

[Aristos Queue]

Sorry to hijack the thread for a moment, but was this work related to LV Embedded, or some other project?

Boredom. To prove to myself that it could be done. And to give me a way to code LV programs while on plane flights without a laptop. Nothing that I've ever turned into functional code. Just a math proof of concept.

[Chris Davis]

Boredom. To prove to myself that it could be done. And to give me a way to code LV programs while on plane flights without a laptop. Nothing that I've ever turned into functional code. Just a math proof of concept.

Thanks :thumbup:

[Jacemdom]

Jacedom:

Were any of the other situations that I posted "interesting cases" for you?

On a conceptual level need for recursion yes, in my present quest no. I

[Jacemdom]

I just encountered a problem that i had to solve using recursion...

I'm working on automaticaly creating a project from a folder hierarchy. I had to think a little bit on what data would i need to do the recursion or stack and then it was as easy as putting a "do what i want while array not empty loop". At each iteration i just use the delete array that automatically gives me the last element by default (wich is feature that i like a lot) and add elements to the stack. I believe that the majority of recursive problems can be solved by that method. Even if there was the possibility to automatically use recursion with VIs, meaning basically an automatic stack creation, is all that effort really needed just to replace a sequence of a couple of clicks (30 seconds) create while loop, create shift register, add delete array, add build array...the rest is needed in both implementations i believe.

If someone does a lot of recursion, he could create a code snippet (i don't remember the exact name in LV) on his pallet with a while loop with shift register and delete array...

[Aristos Queue]

I'm working on automaticaly creating a project from a folder hierarchy. I had to think a little bit on what data would i need to do the recursion or stack and then it was as easy as putting a "do what i want while array not empty loop". At each iteration i just use the delete array that automatically gives me the last element by default (wich is feature that i like a lot) and add elements to the stack. I believe that the majority of recursive problems can be solved by that method.

I do the same thing frequently, but I tend to use the Queue primtives... enqueue the first element, loop while the queue is not empty. On each iteration, dequeue one, then Enqueue the next level. If I need it to be depth-first (stack) then I use the "Enqueue at Other End" prim. I don't know which solution offers better performance.