I was wondering if anyone knew whether the 2k4 robot controller and/or the edu controller would support a recursive algorithm. Obviously, it’d have to be small due to the limitations, but I just want to know if it could work. Thanks!
You would probabally have some trouble with the limitations… If you could use the recursive algorithm you might run into a lot of problems… why are you so interested in using it?
-Greg The Great
Yes, it would definately work. The only realy problem I see is that the PIC controller doesn’t have an overly large stack space, meaning you should make a point of not getting too deep into the recursion. Otherwise, a function call is a function call is a function call, regardless of whether it originated from itself or from a separate function.
unfortunatly, i realize that i cant go too deep. thank you.
but, given the language/compiler i’m also wondering, when i do the recursion, will the variables within the function allocate new memory every time? or will it use the same memory address for the local variables for all the calls?
Yeah, I think the hardware stack is 32 bytes, so subtract a few from already nested CALLs and you can get about 28 recursions. I doubt you’d need or use that many though.
For your second question, it depends on what modifier the variables have in front of them. See the compiler docs in your mcc18/docs folder.
The auto modifier is the default one (it’s default by default, you can make static default if you want). Auto variables are the ones you are used to. They just get shoved somewhere in memory when you declare them and go away when they lose scope. So with recursive functions if you have a bunch of auto variables you allocate new memory for them each recursive call. That way when you leave the recursive function the original varaibles are still intact.
The static modifier defines them globally, but they have the same scope as an auto variable. So if you define them in a function you can only access them in that function, but the variable never gets deallocated, so you can transfer the same value from one function call to the next.
The above 2 are the same as ANSI specs. The compiler also adds one called overlay, which is like static except you can reinitialize it each time the function is called. If you have “static int a = 1;” in a function, a is only given the value 1 when it is declared, and not every time the function is called. “overlay int a = 1;” will set a to 1 each time. There is more stuff on overlay in MPLAB-C18-Users-Guide.pdf. Note that overlay cannot be used in functions called recursively (from the docs).
The stack size is actually 31 words, not 32 bytes, but the principle is the same. Also keep in mind that you probably can’t do the full 31 calls since chances are the initial call to your recursive function already had some stuff on the stack. For example, in the following sequence of calls, 3 stack frames are already used before it even gets to the recursive method. Also, be careful when using interrupts, since an interrupt will also push a frame onto the stack, and if you’ve already used up the entire stack with recursive calls, you’ll get a stack overflow exception.
int main(){
user_code();
}
void user_code(){
doAuto();
}
void doAuto(){
recursiveFn();
}
void recursiveFn(){
recursiveFn();
}
Oh right, I don’t know why I stuck the word bytes on there. I meant 31 locations, each which store 21 bits.
recursion
recursion is
recursion is evil
recursion is evil I
recursion is evil I tellya
Recursion is a bad pracice on any platform and should be avoided. The PIC will crash after something like 28 levels of function calls. You should read up on the stack and how it works. Basically there is something called the stack, which can be thought of as well… a stack. A stack of books or plates or whatever floats your boat. The stack is used to keep track of function calls interrupts etc. Whenever a function is called, the memory address of whatever the processor was doing before the function call is “pushed” onto the top of the stack. The processor then jumps to the function and executes its code. When the function returns the stack is “popped”, cuasing the processor to jump back to where is was before the function call. When functions are called inside of functions, multiple entries are made to the stack. The problem with recursion is is that the stack is a limited resource and eventually it overflows.
That statement is completely false. The use of recursion completely depends on the problem at hand.
For example, the non-recursive solution to the classic Towers of Hanoi problem is significantly more complicated than the recursive solution.
Or, a non-recursive program to find and show the correct path through a maze is significantly more difficult to implement than the recursive solution.
Recursion is an essential technique for any application which uses a tree data structure. I’ve written several web application that require directory traversal… without recursion, these would have been near impossible.
I’m not going to disagree with you that recursion is a bad practice on the robot controller due to its limited memory and stack, but to state that recursion is a bad practice and should be avoided is completely false. There are advantages and disadvantages to recursive algorithms vs. iterative algorithms - in some cases, the recursive solution is better than the iterative solution, in other cases, it isn’t. It depends completely upon the problem at hand.
Originally Posted by Rickertsen2
Recursion is a bad pracice on any platform and should be avoided…
Sorry, but I must put my two cents in as well. You must not program in Scheme! It’s a very lovely langauge, but as far as iterative algorithms go, you’re dead in the water – you must use recursion (well, there is a difference between recursive procedures and recursive proceses, and scheme implements a lovely thing known as tail-end recursion). Anyway, my point, if you want to be schemer, you better recurse. Favorite quote: “To iterate is human; to recurse is divine.”
I totally disagree. When you have the resources, recursion is an invaluable tool. It’s the heart of Deep Blue’s chess game, Google’s page ranking system, and the fastest sorting algorithm ever written. Although looping is usually more efficient, recursion is much simpler, and once you figure out how to do something recursively it’s often very easy to write a loop that does the same thing.
That said, using recursion or looping in your FIRST code is probably a bad idea. Aside from recursion’s stack problems, both methods can eat up a lot of time if you’re not careful, which would slow down your robot’s reflexes. Also, I can’t see what you’d need it for! Most of what your robot does is reacting to stuff, not calculating.
~~Aaron
Edit:
Oops, I just saw Dan’s post where he says the same thing. Go Dan! Way to steal my thunder… 
http://www.kernelthread.com/hanoi/
Yes, recursion is very helpful for the path finding algorithm. 
Though, I am rather unimpressed with the stack size of the Microchip products. The 16 bit motorolla microprocessor that I implemented said pathfinding algorithm on was nice because the stack could be of any size (up to the limit of RAM).
Back towards the topic… Recursion can greatly simply many algorithms. Fibonachi is a good example of that. Infact implementing fibonachi as recersive and iterative tends to be a common problem given by CS-101 professors, to help illustrate recursion.
Though however, with recursion you can trade simplified code(and possibly faster) for increased memory useage. So, to sum up slightly, the use of recursion, iteration, (or anything else) really needs to be determined based on what your goals are (speed, size, time to impliment) and what resources you have available.
Of course that summary could be applied to any engineering decision.
I dont think recursion has any real advantages - its simply a sloppy (lazy?) method of performing certain functions for people who forget that
SW = ALGORYTHMS + DATA STRUCTURES
if you use simple data structures, then yes recursion makes the code look cleaner and simpler
but with a well thought out data structure, there is nothing you can do with recursion that you cant do better without it.
The thing about recursion is, most SW programmers are oblivious to what happens when you call a function - more gets pushed on the stack than the return address, some processors or operating systems push a ton of junk on the stack, and then you have to pull it all back off
remember that the variables you see in higher level languages (like C) most likely are not registers in the uP, they are probabally memory locations assigned or created by the compiler.
Ok ok. I can see we all seem to like recursion. The more i think about it, recursion may have advantages under certian circumstances, but don’t do it on the RC.
I bet you could simulate a stack on RAM and get one with more size. It would take some work, and you would need to know some asm to do it, but I think it’s entirely possible. Rather than using call to jump to the function, which pushes the PC onto the stack, you could just use goto, which just jumps striaght there. Storing variables gets harder though.
I doubt it’s worth the effort. Just watch STKPTR<4:0> and make sure your recursive function stops recursing if it sees the stack is near full.
Rather than using call to jump to the function, which pushes the PC onto the stack, you could just use goto, which just jumps striaght there.
If we’re talking about useless things, might as well hit on the GOTO command. Why use goto for that situation instead of just using a for or while loop or any of their variations (for(;;), while(1), do-while, etc.)? Goto is a useless command. I cannot think of one situation where the taske cannot be better performed with some sort of loop. As far as i know, there has only been one situation found where go must be used to get the desired effect, i.e. break, continue, or loops will not work, and that was discovered by some fulltime programmer who was dedicating his time to finding it. So, to close up a long winded soapboxing, don’t use goto.
edit: ok, that’s not supposed to be a winking smiley, but a semicolon then a closed parenthesese, just accept it. Smilies… arggh!
edit #2: as i clicked ok, i realized there was a disable smilies button, so now it works.
Break and continue are simply a goto command in disguise. Break and continue should be avoided for the same reasons that goto should. The reason that software engineers really hate goto (and break and continue for that matter) is that it generally makes code harder to read. However, there are times where a well-placed goto can simplify code and make it easier to understand than it would be if you had to wrap it in a bunch of if() or for() statements.
{soapbox}
Recursion is a bad pracice on any platform and should be avoided.
Goto is a useless command.
I work full time as an embedded software engineer, and I still wouldn’t feel comfortable making statements like these. While I agree that gotos and recursion are generally a bad practice, I know that there’s a nearly infinite amount of software engineering situations that I haven’t encountered yet, and one or both of these methods may be the best solution in that situation. I’m very encouraged to see so many young people on this board taking such an interest in engineering (and software engineering in particular), and the amount that you all know about these fields already is amazing. However, do you really feel that you guys have enough experience to back these statements up?
I hope that this post doesn’t offend anyone, and if it does I apologize. I am really impressed at the level and intelligence of discussion that occurs on this board. I’m just concerned that the level of misleading information around here seems to be on the rise. There’s a lot of teams that are going to go through a bit of a software engineering trial-by-fire this year with the C based controller, and I just don’t want to see the situation made worse by providing them with bad information when they come here for help.
{/soapbox}
By the way, I didn’t mean the C command goto, I was talking about the asm command goto.
In asm the only way of “looping” is with goto’s or branches.
I think the idea of goto being bad coding practice comes from BASIC. Programs with large numbers of gotos get incredibly confusing to read, since there really is no flow in the program. The program can just jump to any other point without warning and the reader is left wondering why, especially in BASIC with line numbers and statements like “GOTO 150.”
for and while loops help to keep everything structured and easy to follow. Break and continue interrupt that flow, but they made their way into the higher level languages because they are useful and simplify code a lot.
Can you imagine trying to break out of a loop without break? You would need a flag, and all the code after the point you wanted to break from would have to be under an if statement to check to see whether the break flag has been set to true. It could get quite ugly.
Basically, a lot of goto’s in a program is probably a bad idea, but they can be useful in certain situations. If you can find a way to do it without goto’s that doesn’t hurt performance a lot, do it.
The reason that recursion is bad is that when it fails your stack overflows, and that is one of the failure modes that result in unpredictable behavior - its very difficult to debug, because the SW simply looses its mind
GOTO statements are bad because a function or subroutine should have one entry point and one exit point - GOTO is used when you dont really know what you are doing- when you havent really worked out the inputs, output and processing that has to happen to get the outputs from the inputs - its an indication that the programmer started writing code BEFORE he figured out what the code had to do (failed to do the high level design work first)
in all the SW programming classes I took, if you used a goto statement, or you used recursion, or self modifying code, you got an automatic F on whatever that code was for, a project, a quiz, or the final exam -
its not something to avoid, its something you should never use - if you cant figure out how to parse your input, or navigate your data structures without using these shortcuts, then you need to go back and work on your data structures and algorythms somemore.
There are HW equivalents too, like gating a clock, using one shot timers, or circuits that can generate glitchs. The shortcut you make is not worth the problems you will have when the system becomes unstable, or crashes, and you have no idea where to start looking for the cause.