LabVIEW
VI of the Day (9/14/2009) - Recursion
As you might have guessed from the title, a certain shipment has arrived from NI. There are about 3 VIOTD I wanted to do immediately upon arrival, but since two of them are new or much improved in LV8.6, I am choosing "Recursion" for the big day. Recursion is not a function, control, or VI, more of a state-of-mind. It lets you do something you may not have known you wanted to, use a VI on its own BD. As crazy as this sounds, this simple idea allows you to greatly simplify many algorithms.
A classic example (also given by NI) is the calculation of the Fibonacci numbers. This is very easy to do with recursion (and without), but what NI doesn't really mention is that it is a terrible method for actually calculating the numbers. Many calculations are redundant and you end up with an algorithm that grows exponentially with N. This can be helped using a lookup table to avoid these redundancies, and the lookup table is a very good application for a recursive VI. However, I believe that variants are a very efficient mechanism for generating and using lookup tables, and after some testing I'll show some examples of improved recursion in a different VIOTD.
Our favorite looping constructs are around partly because early compilers and interpreters could not deal well with recursion. Have you ever wanted to generate an array of numbers without using a for-loop, the first example does just that using recursion. Works great, for arrays of several thousand or less. No range checking or anything like that, just a little toy to show you what linear recursion is about.
(I am sure all kinds of things go wrong if you try to create a recursive VI with a snippet, just practicing).
A second example for today showing tree recursion. This is implementing a divide-and-conquer algorithm. These algorithms are a much better use of recursion and can really make your code compact and readable. They are often a bit inefficient, but a lot of times I find myself with a problem where I need a simple answer and not a super-efficient code that is going to be constantly reused. A quick example this morning: How many ways can you make change for a dollar with pennies, nickels, dimes, quarters and half-dollars? I solve this using a recursive algorithm, each step I divide the problem into two parts: number of ways to make change without using a particular coin and the number of ways to make change for the remaining amount when I use one of a given coin. Example: How many ways to make change for a dollar without quarters + how many ways to make change for 75 cents. In one case I reduce the number of coins, in the second case I reduce the amount. As it iterates, the algorithm keeps reducing the problem until it succeeds (makes change) or fails (runs out of coins or reaches a negative amount).
If you don't have LV2009, you can still try to write the change making code without using recursion and let me know how much trouble it is (I haven't tried).
VIOTD groundrules here.
