19

The Arduino Uno board has limited RAM which means it has a limited call stack available. Sometimes, recursion is the only quick option to implement a certain algorithm. So, given that the call stack is severely limited, what would be a way to find out that given a certain program running on the board, exactly how many recursive calls can you afford before there is a stack overflow (and bad things happen)?

  • 2
    Can you give an example of an algorithm where the choice between a recursive and non-recursive solution is so clear cut? – Cybergibbons Feb 23 '14 at 9:52
  • 1
    @Cybergibbons Most recently, I had to write and test RDP in a short time span, so I went ahead with the recursive implementation. I am not saying that iterative is not possible, just that it may be easier to go ahead with the recursive version. – asheeshr Feb 23 '14 at 10:07
  • What does this mean in the question title: How much ca!@#QFSD@$RFW? I'm curious as to why no-one has edited that out to be something more meaningful (in the last 4 years). – Nick Gammon Mar 24 '18 at 2:24
  • The answer is 211 times (depending on many factors) :). See my answer here: arduino.stackexchange.com/a/51098/7727. @NickGammon, he is pretend "cursing" I think. It is a play on word for "recurse". Took me a minute to figure that out too. Was pretty confusing at first. – Gabriel Staples Mar 24 '18 at 2:34
  • Oh I see. I thought the SE servers might have had a glitch :) – Nick Gammon Mar 24 '18 at 3:07
15

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:

SRAM organization

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.

  • I see peter-r-bloomfield posted his answer while I was writing mine; his answer looks better as it fully describes the content of the stack after a call (I had forgotten the registers state). – jfpoilpret Feb 23 '14 at 10:23
  • Both very good quality answers. – Cybergibbons Feb 23 '14 at 11:18
  • Static data = .bss + .data, and is what is reported by Arduino as "RAM taken up by global variables" or whatever, correct? – Gabriel Staples Mar 24 '18 at 5:24
  • 1
    @GabrielStaples yes exactly. In more detail .bss represents the global variables with no initial value in your code, whereas data is for global variables with an initial value. But in the end they use the same space: Static Data in the diagram. – jfpoilpret Mar 24 '18 at 7:50
  • 1
    @GabrielStaples forgot one thing, technically these are not only global variables going there, you also have variables declared static within a function. – jfpoilpret Mar 24 '18 at 7:52
8

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.

  • Some of the more high-end compilers, such as IAR (who do support AVR) and Keil (who do not support AVR) have tools to help you monitor and manage stack space. It's really not advisable on something as small as an ATmega328 though. – Cybergibbons Feb 23 '14 at 9:59
7

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.

  • 1
    avr-gcc does not support tail recursion. – asheeshr Feb 23 '14 at 10:08
  • @AsheeshR - Good to know. Thanks. I figured it was probably unlikely. – Peter Bloomfield Feb 23 '14 at 10:10
  • You can do a tail call elimination/optimization by refactoring your code instead of hoping the compiler will do it. As long as the recursive call is at the end of the recursive method you can safely re-write the method to use a while/for loop. – abasterfield Feb 23 '14 at 13:32
  • 1
    The post by @TheDoctor contradicts "avr-gcc does not support tail recursion", as does my test of his code. The compiler did indeed implement tail recursion, which is how he got up to a million recursions. Peter is correct - it is possible for the compiler to replace call/return (as the last call in a function) with simply jump. It has the same end result and does not consume stack space. – Nick Gammon Jul 7 '15 at 5:17
2

I had this exact same question as I was reading Jumping into C++ by Alex Allain, Ch 16: Recursion, p.230, so I ran some tests.

TLDR;

My Arduino Nano (ATmega328 mcu) can do 211 recursive function calls (for the code given below) before it has a stack overflow and crashes.

First off, let me address this claim:

Sometimes, recursion is the only quick option to implement a certain algorithm.

[Update: ah, I skimmed the word "quick". In that case you have some validity. Nevertheless, I think it's worth saying the following.]

No, I don't think that is a true statement. I'm pretty certain all algorithms have both a recursive and a non-recursive solution, without exception. It's just that sometimes it is significantly easier to use a recursive algorithm. Having said that, recursion is very much frowned upon for use on microcontrollers and would probably never be allowed in safety-critical code. Nevertheless, it is possible of course to do it on microcontrollers. To know how "deep" you can go into any given recursive function, just test it! Run it in your real-life application in a real-life test case, and remove your base condition so that it will infinitely recurse. Print out a counter and see for yourself how "deep" you can go so you know whether or not your recursive algorithm is pushing the limits of your RAM too close to be used practially. Here's an example below to force stack overflow on an Arduino.

Now, a few notes:

How many recursive calls, or "stack frames" you can get is determined by a number of factors, including:

  • The size of your RAM
  • How much stuff is already on your stack or taken up in your heap (ie: your free RAM matters; free_RAM = total_RAM - stack_used - heap_used, or you might say free_RAM = stack_size_allocated - stack_size_used)
  • The size of each new "stack frame" which will be placed onto the stack for every new recursive function call. This will depend upon the function being called and its variables and memory requirements, etc.

My results:

  • 20171106-2054hrs - Toshiba Satellite w/16 GB RAM; quad-core, Windows 8.1: final value printed before crash: 43166
    • took several seconds to crash--maybe 5~10?
  • 20180306-1913hrs Dell high-end laptop w/64 GB RAM; 8-core, Linux Ubuntu 14.04 LTS: final value printed before crash: 261752
    • followed by the phrase Segmentation fault (core dumped)
    • took only ~4~5 sec or so to crash
  • 20180306-1930hrs Arduino Nano: TBD---is at ~250000 and still counting---the Arduino optimization settings must have caused it to optimize out the recursion...??? Yes, that is the case.
    • Add #pragma GCC optimize ("-O0") to the top of the file and redo:
  • 20180307-0910hrs Arduino Nano: 32 kB flash, 2 kB SRAM, 16 MHz processsor: final value printed before crash: 211 Here are the final print results: 209 210 211 ⸮ 9⸮ 3⸮
    • took only a fraction of a second once it started printing at 115200 serial baud-rate--maybe 1/10 sec
    • 2 kiB = 2048 bytes / 211 stack frames = 9.7 bytes/frame (assuming ALL of your RAM is being used by the stack--which actually isn't the case) --but this seems very reasonable nonetheless.

The code:

The PC application:

/*
stack_overflow
 - a quick program to force a stack overflow in order to see how many stack frames in a small function can be loaded onto the stack before the overflow occurs

By Gabriel Staples
www.ElectricRCAircraftGuy.com
Written: 6 Nov 2017
Updated: 6 Nov 2017

References:
 - Jumping into C++, by Alex Allain, pg. 230 - sample code here in the chapter on recursion

To compile and run:
Compile: g++ -Wall -std=c++11 stack_overflow_1.cpp -o stack_overflow_1
Run in Linux: ./stack_overflow_1
*/

#include <iostream>

void recurse(int count)
{
  std::cout << count << "\n";
  recurse(count + 1);
}

int main()
{
  recurse(1);
}

The Arduino "Sketch" program:

/*
recursion_until_stack_overflow
- do a quick recursion test to see how many times I can make the call before the stack overflows

Gabriel Staples
Written: 6 Mar. 2018 
Updated: 7 Mar. 2018 

References:
- Jumping Into C++, by Alex Allain, Ch. 16: Recursion, p.230
*/

// Force the compiler to NOT optimize! Otherwise this recursive function below just gets optimized into a count++ type
// incrementer instead of doing actual recursion with new frames on the stack each time. This is required since we are
// trying to force stack overflow. 
// - See here for all optimization levels: https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html
//   - They include: -O1, -O2, -O3, -O0, -Os (Arduino's default I believe), -Ofast, & -Og.

// I mention `#pragma GCC optimize` in my article here: http://www.electricrcaircraftguy.com/2014/01/the-power-of-arduino.html
#pragma GCC optimize ("-O0") 

void recurse(unsigned long count) // each call gets its own "count" variable in a new stack frame 
{
  // delay(1000);
  Serial.println(count);

  // It is not necessary to increment count since each function's variables are separate (so the count in each stack
  // frame will be initialized one greater than the last count)
  recurse (count + 1);

  // GS: notice that there is no base condition; ie: this recursive function, once called, will never finish and return!
}

void setup()
{
  Serial.begin(115200);
  Serial.println(F("\nbegin"));
  // First function call, so it starts at 1
  recurse (1);
}

void loop()
{
}

References:

  1. Jumping into C++ by Alex Allain, Ch 16: Recursion, p.230
  2. http://www.electricrcaircraftguy.com/2014/01/the-power-of-arduino.html - literally: I referenced my own website during this "project" to remind myself how to change Arduino compiler optimization levels for a given file with the #pragma GCC optimize command since I knew I had it documented there.
  • 1
    Note that, according to the docs of the avr-lib, you should never compile without optimization anything that relies on the avr-libc, as some thing are not guaranteed to even work with optimization turned off. I thus advice you against the #pragma you are using there. Instead, you may add __attribute__((optimize("O0"))) to the single function you want to unoptimize. – Edgar Bonet Mar 25 '18 at 16:44
  • Thanks, Edgar. Do you know where AVR libc has this documented? – Gabriel Staples Mar 25 '18 at 19:01
  • 1
    The documentation on <util/delay.h> states: “In order for these functions to work as intended, compiler optimizations must be enabled [...]” (emphasis in original). I'm not quite sure whether any other avr-libc functions have this requirement. – Edgar Bonet Mar 25 '18 at 20:05
1

I wrote this simple test program:

void setup() {
  // put your setup code here, to run once:
  Serial.begin(115200);
  recurse(1);
}

void loop() {
  // put your main code here, to run repeatedly: 

}

void recurse(long i) {
  Serial.println(i);
  recurse(i+1);
}

I compiled it for the Uno, and as i write it has recursed over 1 million times! I don't know, but the compiler may have optimized this program

  • Try to return after a set number of calls ~1000. It should create a problem then. – asheeshr Feb 23 '14 at 16:04
  • 1
    The compiler has cunningly implemented tail-recursion on your sketch, as you will see if you disassemble it. What this means is that it replaces the sequence call xxx / ret by jmp xxx. This amounts to the same thing, except that the compiler's method does not consume the stack. Thus you could recurse billions of times with your code (other things being equal). – Nick Gammon Jul 7 '15 at 5:14
  • You can force the compiler not to optimize out the recursion. I'll come back and post an example later. – Gabriel Staples Mar 24 '18 at 1:20
  • Done! Example here: arduino.stackexchange.com/a/51098/7727. The secret is to prevent optimization by adding #pragma GCC optimize ("-O0") to the top of your Arduino program. I believe you have to do this at the top of each file you want it to apply to--but I haven't looked that up in years so research it for yourself to be sure. – Gabriel Staples Mar 24 '18 at 2:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.