Recursion?

[Phasmatis568]

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!

[GregTheGreat]

Originally Posted by Phasmatis568

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

[rbayer]

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.

[Phasmatis568]

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?

[Jay Lundy]

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).

[rbayer]

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();
}

[Jay Lundy]

Originally Posted by rbayer

The stack size is actually 31 words, not 32 bytes

Oh right, I don't know why I stuck the word bytes on there. I meant 31 locations, each which store 21 bits.

[KenWittlief]

recursion
recursion is
recursion is evil
recursion is evil I
recursion is evil I tellya

[Rickertsen2]

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.

[DanL]

Originally Posted by Rickertsen2

Recursion is a bad pracice on any platform and should be avoided....

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.

[mtrawls]

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."

[Mercutio]

Originally Posted by Rickertsen2

Recursion is a bad pracice on any platform and should be avoided.

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... [/edit]

[Random Dude]

Originally Posted by SuperDanman

For example, the non-recursive solution to the classic Towers of Hanoi problem is significantly more complicated than the recursive solution.

http://www.kernelthread.com/hanoi/

Originally Posted by SuperDanman

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.

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.

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.

[KenWittlief]

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.

[Rickertsen2]

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.