How much can I recurse? How much can I recurse? How much ca!@#QFSD@$RFW

If you really want to recurse (and as @jippie said it is a bad idea; subliminal message: don't do it) and want to know how much you can recurse, then you will have to perform some calculation and experiments; also you generally will have only an approximation of it as it depends a lot on the memory state at the time your recursive function will be called.

For this, you should first know how SRAM is organized inside AVR-based Arduino (it won't apply to e.g. the Arduino Galileo by Intel). The following diagram from Adafruit shows it clearly:

Then you need to know the total size of your SRAM (depends on Atmel MCU, hence what kind of Arduino board you have).

On this diagram, it is easy to find out ths size of Static Data block as it is known at compile-time and won't change later on.

The Heap size can be more difficult to know as it can vary at runtime, depending on dynamic memory allocations (malloc or new) performed by your sketch or the libraries it uses. Using dynamic memory is quite rare on Arduino, but some standard functions do it (type String uses it, I think).

For the Stack size, it will also vary during runtime, based on the current depth of function calls (each function call takes 2 bytes on the Stack to store the address of the caller) and the number and size of local variables including passed arguments (that are also stored on the Stack) for all the functions called until now.

So let's suppose your recurse() function uses 12 bytes for its local variables and arguments, then each call to this function (the first one from an external caller and the recursive ones) will use 12+2 bytes.

If we suppose that:

• you are on Arduino UNO (SRAM = 2K)
• your sketch does not use dynamic memory allocation (no Heap)
• you know the size of your Static Data (let's say 132 bytes)
• when your recurse() function is called from your sketch, the current Stack is 128 bytes long

Then you are left with 2048 - 132 - 128 = 1788 available bytes on the Stack. The number of recursive calls to your function is thus 1788 / 14 = 127, including the initial call (which is not a recursive one).

As you can see, this is very difficult, but not impossible to find what you want.

A simpler way to get the stack size available before recurse() is called would be to use the following function (found on Adafruit learning center; I have not tested it myself):

int freeRam () 
{
  extern int __heap_start, *__brkval; 
  int v; 
  return (int) &v - (__brkval == 0 ? (int) &__heap_start : (int) __brkval); 
}

I strongly encourage you to read this article at Adafruit learning center.

Recursion is bad practice on a microcontroller as you already stated yourself and you probably want to avoid it whenever possible. On the Arduino site there are some examples and libraries available for checking free RAM size. You can for example use this to figure out when to break recursion or a bit trickier/riskier to profile your sketch and hard code the limit in it. This profile would be required for every change in your program and for every change in Arduino tool chain.

It depends on the function.

Every time a function is called, a new frame is pushed onto the stack. It will usually contain various critical items, potentially including:

• Return address (the point in the code from which the function was called).
• The local instance pointer (this) if calling a member function.
• Parameters passed into the function.
• Register values which need to be restored when the function ends.
• Space for local variables inside the called function.

As you can see, the stack space required for a given call depends on the function. For example, if you write a recursive function which only takes an int parameter and uses no local variables, it won't need much more than a few bytes on the stack. That means you can recursively call it far more than a function which takes several parameters and uses a lot of local variables (which will eat up the stack much quicker).

Obviously the state of the stack depends on what else is going on in the code. If you start a recursion directly within the standard loop() function, then there probably won't be a lot on the stack already. However, if you start it nested several levels deep in other functions, then there won't be as much room. That will affect how many times you can recurse without exhausting the stack.

It's worth noting that tail recursion optimisation exists on some compilers (although I'm not sure if avr-gcc supports it). If the recursive call is the very last thing in a function, it means it is sometimes possible to avoid altering the stack frame at all. The compiler can just re-use the existing frame, since the 'parent' call (so to speak) is finished using it. That will mean you can theoretically keep recursing as much as you like, so long as your function doesn't call anything else.