--- In [email protected], Mickey Mathieson <[EMAIL PROTECTED]> wrote: > > --- crasypantz <[EMAIL PROTECTED]> wrote: > > > I think I've seen in the past (maybe not here, but > > probably) much debate regarding the good, the bad, > > and the ugly of programming using recursion. > > I don't know that I ever saw a final verdict. I am > > curious if the argument changes when talking about > > the embedded world. I have a project and the most > > straightforward and efficient (as I see it at least) > > solution is to use recursion. A friend said he'd > > heard 'recursion equals bad' in the embedded > > environment. I know there are many savvy minds here > > so if there is a good argument why recursion should > > or needs to be avoided then please could someone > > offer a little insight with valid reasons instead > > of me just going with what someone > > 'heard'? Any help is appreciated. Thanks. > > If program size is an issue and the recursive function > is less code than non recursive function - This would > be a reason the use a recursive function.
At the same time, if stack size is very tight, recursion _may_ be a bad approach for one simple reason: if the recursive algorithm takes up lots of stack space (assuming that the target environment actually has a CPU stack, so please let's not discuss this assumption too much), then you may end eating up stack space when it might have been better to "unfold" the recursive algorithm partially. Let's look at one typical (purely theoretical) example, the Ackermann function: as far as I know it's been invented to show that careless recursion is an evil breed. However, it's also an excellent example that some recursive functions can be unfold into an iterative algorithm with very little effort. In effect, if I recall correctly, the Ackermann function only needs some sort of "powering the power"; that means, the number/level of powers of one single base increases over the parameters, and that's it. So a simple "for" loop will do (in terms of C/C++/Java). Recursion is not bad in itself. Careless recursion can easily lead to even worse programs than careless programming in general. So, without knowing your requirements more exactly we cannot give a more educated advice. Maybe if you tell us the challenge together we can find a really nifty solution which eliminates the worse parts of recursion? As a real-life example: in a database, I had to unfold a linked chain of records in a table; one record might point to another one, this one might point to yet another one, and so on. A typical example of recursive database queries. What have I done? I have taken an auxiliary table and filled it during the first run of the query with all records which did have a successor, together with a "level" value of 1; all records without a successor have a "level" value of 0. This "level" value is a global variable (in my context). Now in the next run I only read those records from the auxiliary table which have a "level" value of 1. Those which have a successor in the original DB table are now written to the auxiliary table with a "level" value of 2. And so on and so on; every new run of the query retrieves the next level of "nesting" (actually singly-linked lists) from the original table with the help of the auxiliary table. And eventually all chains are stored in the auxiliary table. O.k., this was a bit short and didn't get to the real point (namely the data I had to actually retrieve from the original table), but the principle shows that even with tools which don't allow recursion you can (with a little external effort) resolve recursive queries. So we might be able to find a "less recursive" solution for you which might be the "optimal" solution for you because it will eat up neither much stack space nor much heap space. [I know, C and C++ don't have the concepts of stack and heap, I just wanted to point out my thoughts clearly and easily.] Regards, Nico
