recursive functions on a mcu - is this bad?

[Admin]

I remember back in the day that recursive functions are an extremely bad thing (and sometimes impossible thing) to do on a microcontroller.

That said, I've been doing it recently for a GUI system without problems . . . but I'm worried about longterm software crashing from memory leaks and stack overflows . . . I'm using my Axon II for this and not sure just how gcc treats recursive functions.

Is this bad?

Code: [Select]

void main(void)
     {
     run_GUI();
     }
void run_GUI(void)
     {
     do_something();//just rewrites a variable
     run_GUI();
     }

(I'm a weak programmer, I know )

[KurtEck]

The simple answer is it depends...

That is each call will eat so many bytes of stack space, including: return address, saved registers and assuming you have any local variables a stack frame that is large enough to hold all of your locals...  So if you recurse very many times it can eat up your stack space pretty quickly.

Likewise if it is something like your mainline that never returns, you will have all of the original stack frame associated with the first call that will never get reclaimed.

Do I use recursion?  Sometimes but only for specific type things.
Kurt

[Webbot]

Its not a GCC problem - the compiler will do what you ask.

But as KurtEck says the restriction is that everytime you call ANY other function then space is required on the stack (to remember where to return to as well as for any local variables).

Micro-controllers have a limited amount of RAM compared to PCs.
The compiler assigns memory slots for global variables starting at the beginning of RAM. This is a fixed size as any program has a fixed number of global variables.
When running the program the stack starts at the end of your RAM and grows downwards. Every time you call another function then it will grow downwards until that function returns.
The problem at runtime comes about when the stack grows downwards so far that it 'meets' your global variables and starts overwriting them - normally with catastrophic result (ie a crash).
Bear in mind that if an interrupt occurs then the stack will grow downwards even further until the interrupt handling routine has finished.

So your code snippet ...

Code: [Select]

void main(void)
     {
     run_GUI();
     }
void run_GUI(void)
     {
     do_something();//just rewrites a variable
     run_GUI();
     }

... would be a disaster as 'run_GUI' keeps calling 'run_GUI' which never returns. So the stack will keep filling up and eventually go bang. This is also true if it was running on a PC - its just that it would take longer as the PC has a bigger stack. Most PC code checks for this stuff and you would get a 'Stack Overflow' error.

So a routine that is called recursively must have an exit. For example:

Code: [Select]

void main(void){
     run_test(5);
}
void run_test(int n){
   print n;
   n = n - 1;
   if(n >= 0){
       run_test(n);
   }
}
would be ok as the 'run_test' routine exits once n < 0. So it would be called recursively up to a depth of 5 times.


However:

Code: [Select]

void main(void){
     run_test(32000);
}
would probably fail as it would be called recursively to a depth of 32000 times. ie it would need to remember 32000 return addresses where each one is 2 bytes. So unless you have around 64k of available memory (ie once you subtract the amount used by your global variables) then it will fail.
 

[Admin]

I guess for a small GUI on an mcu thats power cycled often its not a problem. The recursiveness just made programming the GUI easier, so thats why I went with it.


While we're at it, one more question . . . what does the return do in this situation? Does it only exit do_something(), or does it cause "something" to be printed?

(I could just try it on an mcu, but I don't have anything available at the moment to test )

Code: [Select]

void main(void)
     {
     run_GUI();
     rprintf("something");
     }
void run_GUI(void)
     {
     while(1)
          do_something();
     }
void do_something(void)
     {
     return;//what does this line do, exactly?
     }

[Webbot]

It only causes the current function 'do_something' to be exited and goes back to whatever called it ie the 'run_GUI' routine.
So in your example: the program will NEVER get as far as the 'rprintf' command

[Admin]

Is there a 'forget all recursive history' line of code I can call, or do I have no choice but to finish a function to fully 'exit' it?

(I'm guessing there isn't )

[Webbot]

In a word - No.

Just make sure the 'do_something' routine returns a value which is then tested in 'run_GUI' and can make 'run_GUI' return if a specific value is met.

Alternatively: and horribly.

Code: [Select]

int getOutOfHere = 0;

void main(void) {
     run_GUI();
     rprintf("something");
}
void run_GUI(void) {
     while(1){
          if(getOutOfHere){
               return;
          }
          do_something();
     }
}
void do_something(void){
     if( blah blah){
         getOutOfHere = 1;
     }
     return;//what does this line do, exactly?
}

[cyberfish]

What you are doing here is called tail recursion (http://en.wikipedia.org/wiki/Tail_recursion). In this case, a while loop, like suggested above, would be better.

It's a fairly beginner thing to do, and sometimes the compiler can recognize it and change it to a loop for you, but don't rely on that.

The way you have it written, it will inevitably eventually crash. Very bad. Faster if you clock the MCU higher, or stack is smaller, etc. It may crash every hour for you now, but if you later decide to port it to a 2x faster MCU, it will crash in half an hour. Or maybe you decide to add a local variable and make the frame size bigger, so it will crash in a few minutes.

Just don't do it.

[cyberfish]

And to answer the title, there is nothing wrong with recursion, as long as you know how much RAM it will use, and how deep it will go.

Infinite recursion is bad, always, because it requires infinite amount of RAM, which we don't have.

[KurtEck]

Is there a 'forget all recursive history' line of code I can call, or do I have no choice but to finish a function to fully 'exit' it?

(I'm guessing there isn't )

I agree with webbot here the simple and best answer is no.

But, If you would like to use a lot of memory and bring in lots of code, you could see if the GCC on the AVRs support structured exception handling  . Please forgive that I may not have the syntax correct as I have never used these on this platform nor used them period for over a decade...

Code: [Select]

void main(void)
     {
    try
        {
         run_GUI();
        }
    catch
        {
        }
    // continue on...
     }
void run_GUI(void)
     {
     do_something();//just rewrites a variable
     run_GUI();
     }

void do_something(void)
    {
...
     throw(1);
    }

As for your question of what does the return do, it does the reverse of what the call does. Note: on void functions, there is an implied return at the end of the function.

What a simple call does is to push the current(after the call instruction) IP (instruction pointer) onto the stack and then set the IP to the address of the function being called.  When your function starts up, it then typically pushes some if not all of the registers it uses onto the stack.  (There is a convention of which registers that must be preserved by a call and which can be trashed). 

So when your function wishes to return, it then: restores the registers it used, by popping the values off of the stack in the reverse order it pushed them.  It then does the ret instruction, which pops the address of the instruction after the call and places it in the Instruction pointer register where the code continues. 

Now the above gets a little more complicated if your function has local variables and/or enough parameters that requires them to be placed on the stack... If you are interested in that, I would suggest looking at the generated list file (.lss) and see what code is generated.

Kurt

[Webbot]

But, If you would like to use a lot of memory and bring in lots of code, you could see if the GCC on the AVRs support structured exception handling  Roll Eyes  . Please forgive that I may not have the syntax correct as I have never used these on this platform nor used them period for over a decade...

In C its done using the 'setjmp' command in setjmp.h. This is supported by GCC but I haven't tested it. For more info see: http://en.wikipedia.org/wiki/Setjmp.h

But its a very ugly thing to use as it works very differently to exceptions in language like Java where each rolled back routine can perform some clean up code. In setjmp it directly modifes the stack - as if nothing has happened - meaning the rolled back code doesn't get a look in. An example of why this is bad is that if one of the rolled back calls has opened a file, on an sdCard say, then its code to close the file never gets called and so the file may be corrupt. Its very much a low level command and should be used with caution. It also makes the code very difficult to follow.

[cyberfish]

Just to clarify, all the exception business here is a purely academic discussion to answer

Is there a 'forget all recursive history' line of code I can call, or do I have no choice but to finish a function to fully 'exit' it?

We are NOT suggesting using it in this case. Exceptions is not the solution here.

The solution is to get rid of the tail recursion, and make it into a loop, so it can run forever without crashing.

[paulstreats]

I know that you arent using PIC's , but PIC's have a recursion depth or Hardware stack that allows recursions generally around 32 levels deep. You could simply make your function POP the previous recursion level off the stack every time it is run so the stack levels dont accumulate. Is this possible with AVR?

 However it is bad programming....

Try having 1 function that calls the other function provided that it isnt already running.

[cyberfish]

Yeap, just decrement stack pointer by frame size.

But that is VERY bad. Don't even think about doing it!

[paulstreats]

The best answer would be to set up a timer interrupt to call the function provided the function isnt already running (requiring a global boolean variable)

[Admin]

The best answer would be to set up a timer interrupt to call the function provided the function isnt already running (requiring a global boolean variable)

So you're saying an interrupt, that says go to a different function, will let me escape a stack of functions and clear memory?

[KurtEck]

The best answer would be to set up a timer interrupt to call the function provided the function isnt already running (requiring a global boolean variable)

This one completely lost me?  Why is this the best answer? 

Admin: When an event that happens that will trigger an interrupt.  The AVR processor will basically push the address the address of the instruction after the one that received the interrupt and then will look up the address of the function that is defined for that interrupt and jump to it.  When the interrupt function does a return it basically pops the address off the stack and puts it into the instruction pointer register and clears a status bit... The actual code in the interrupt handler has the duty to preserve all of the registers it uses as well as the state register and restore them before it returns to the code that it interrupted. 

So I am somewhat confused on how this helps here. But I could be missing something.

Kurt

[paulstreats]

when the function runs set a variable (functionrunning=1). when the function exits set the variable(functionrunning=0);

(interrupt routine)
if(functionrunning == 0){
 runfunction();
}else{
//function is already running - do nothing
}


this type of thing would probably be better

Code: [Select]


runner(){
functionrunning = 1;
functionrunning = myfunction(); // returns 0
}

int myfunction(){
//your code here
return 0;
}

interruptroutine(){
 if (functionrunning == 0){
  runner();
}else{
//do nothing
}
}


This way the function will only run again once it has exited(and of course the stack pointer decrements when the function exits).

[garrettg84]

Code: [Select]

void main(void)
     {
     run_GUI();
     }
void run_GUI(void)
     {
     do_something();//just rewrites a variable
     run_GUI();
     }


I would say just drop it in a loop as previously suggested.

Code: [Select]

void main(void)
     {
     for (;;)
          {
          run_GUI();
          }
     }
void run_GUI(void)
     {
     do_something();//just rewrites a variable
     }

Provided your variables are properly scoped, there should be no difference between your code and what is suggested. It has been mentioned that you won't need recursion unless you have a way to break out of that recursion or the recursion is needed to return a variable. I often use recursion in taking user input while checking for valid and good data, if no good data is provided I output an error and recurse into the function. Example of when recursion is useful:

Code: [Select]

void main(void)
     {
     //what ever function you'd use to print
     out_Int( get_Char() );
     }
//function that can get called recursively
//returns an integer
int get_Int(void)
     {
     //tmp space for user input
     char tmpIn[];
     //sets the variable to the user input (wherever it comes from...)
     tmpIn = userInputFunction();
     //The conditional to check if the userinput converts to an integer - atoi ASCII to integer
     if ( atoi(tmpIn) )
          {
          //If the user input string converts, return the integer
          return atoi(tmpIn);
          }
     else
          {
          //If the user input string DOESN'T convert (returns a 0 value), return the value of the recursive
          return get_Int();
          }
     }

//function that would print out the integer
void out_Int(int theInt)
     {
     //print theInt
     }
char[] userInputFunction(void)
     {
     //get user input
     }

For what it's worth, most recursion can actually be replaced with a loop as long as there is a testable value. Recursion is typically just a style kind of thing.