# Recursion versus Tail Recursion on an Arduino

In computer science, recursion chews up a valuable and limited resource – the stack – and can lead to an unrecoverable type of runtime error: the dreaded StackOverflow. Tail Recursion however is a form of recursion that doesn’t use any stack space, and thus is a way to use recursion safely.

freeRam() is the function to test the usage of memory

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


I am testing on arduino, in order to see the difference of the memory usage between the recursive way and tail recursive way

// recursive way
int recsum(int x){
if(x==1)
return x;
else
return recsum(x-1) +x;
}

// tail recursive
int tailrecsum(int x, int total){
if(x==1)
return total;
else
return tailrecsum(x-1,total+x);
}


however

void setup() {
Serial.begin(9600);
Serial.println( recsum(1000) );
Serial.println(freeRam());
}


recursion 1000 times outputs still 1858 bytes available

void setup() {
Serial.begin(9600);
Serial.println( tailrecsum(1000, 0) );
Serial.println(freeRam());
}


tail recrusion 1000 times outputs also 1858 bytes available

The test shows the recursion and tail recursion way in arduino doesn't affect the memory usage, so I am very confused and about it and in doubt of my results.

• Tail recursion can always be converted to a loop, which is much more efficient. – stevenvh Jun 28 '12 at 14:39
• The confusion here is why in this test the recursion and tail recursion consumes the same memory, or even say they consumes memory at all. because void setup() { Serial.begin(9600); Serial.println(freeRam()); } will outputs 1858 bytes available in the memory – user824624 Jun 28 '12 at 14:42
• My comment wasn't meant to be an answer, that why I posted as comment. Just to say that tail recursion is a Bad Thing™. When I was a student, using tail recursion would have cost me points on my exams. BTW, some compilers will turn it into a loop. – stevenvh Jun 28 '12 at 14:48
• @stevenh - So I suspect you never used haskell (or any other functional language)? – PetPaulsen Jun 28 '12 at 14:50
• @stevenvh Tail recusion isn't a bad thing, despite what your teachers told you. It's a tool that has its place, and when properly used is a clue to the compiler that a specific optimization can be performed. stackoverflow.com/questions/34125/… Generally in an embedded system, however, recursion of any sort is to be used strictly only when there is no other option, and tail recursion, by definition, has another option - so it's not recommended for embedded systems. – Adam Davis Jun 28 '12 at 16:41

## 3 Answers

In both cases, your setup() function is looking for a memory leak, but there is no memory leak. A recursive function will only increase stack usage as the recursion takes place. Eventually, the stack unwinds until the final return statement executes, leaving the stack as it was when the function was first called, so the free memory after the function call is the same as it was beforehand.

EDIT

At first I thought that your freeMem function checks the amount of memory statically allocated. Adam Davis has pointed-out that this is not the case.

I don't know the Arduino or it's development environment, but the following pseudo-code might help. The general idea is to determine the stack usage just before it "unwinds" ...

int recsum(int x)
{
if(x==1)
{
//Pseudo-code line follows ...
//stack_used = (int)( &top_of_stack - stack_pointer );
return x;
}
return recsum(x-1) +x;
}


This assumes that the stack grows 'downwards', and you will have to look at your documentation to see how to reference the top-of-stack.. You can use your freeMem function but in either case you will have to subtract the stack usage before setup() is called.

• Serial.println( recsum(1000) ); Serial.println(freeRam()); I kind of don't understand , in the program, I use this function, so the recursion should take place, no? – user824624 Jun 28 '12 at 14:55
• By the time the first line has executed, the call to recsum will have completed and returned so the stack will be as it was beforehand. In any case, your freeRam function checks the heap which isn't used anyway. – MikeJ-UK Jun 28 '12 at 14:59
• ok, I got it . is there a function to check the memory usage about stack in arduino? – user824624 Jun 28 '12 at 15:17
• I don't know the Arduino at all but I will edit my answer with some pseudo-code. – MikeJ-UK Jun 28 '12 at 15:19
• @user824624 - I would suggest to call freeRam, when you are about to return from the deepest recursion. In your case, when you check for x == 1. – PetPaulsen Jun 28 '12 at 15:23

Once the function exits back to main, the stack is returned. The function doesn't continue to use the stack once it's finished, so measuring the memory after the function is done won't tell you anything. You need to measure the memory when the recursion is at its deepest point.

For instance, you can create a variable that would keep track of the minimum free ram, and then print that at the end:

int minimumRam = 2048;

static int freeRam () {
extern int __heap_start, *__brkval;
int v;

v = (int) &v - (__brkval == 0 ? (int) &__heap_start : (int) __brkval);

// Test to see if this measurement resulted in lower ram than we've seen before
if(minimumRam > v) minimumRam = v;

return v;
}

// recursive way
int recsum(int x){
freeRam();
if(x==1)
return x;
else
return recsum(x-1) +x;
}

// tail recursive
int tailrecsum(int x, int total){
freeRam();
if(x==1)
return total;
else
return tailrecsum(x-1,total+x);
}

void setup() {
Serial.begin(9600);
Serial.println( recsum(1000) );
Serial.println(minimumRam);
}


Adding a new global variable that keeps track of the minimum ram we've seen, updating that each time we test the ram size, and running that test inside each function call ensures we test it every time the stack changes. Then we print that minimum out at the end and you can find out just how much memory was left when the system was at its minimum.

• But the OP's freeRam() function doesn't check stack allocation. – MikeJ-UK Jun 28 '12 at 15:30
• @MikeJ-UK Look again. What is the value of &v ? Personally I prefer looking at the actual value of the stack pointer, (uint8_t *)(SP) but creating a stack variable and looking at its memory location is certainly acceptable for generic measurements of this type. – Adam Davis Jun 28 '12 at 15:30
• Ahhh! - I was mentally 'seeing' static int v. I assume the heap and stack grow in opposite directions then. – MikeJ-UK Jun 28 '12 at 15:32
• @MikeJ-UK For the arduino the stack starts at the top - 0x7FF in the case of an Uno - and "grows" downward towards 0x000. The heap starts at the bottom - 0x000 in this case - and grows upward toward 0x7FF. You only have problems when they run into the same area simultaneously. Careful stack management means you can use a large stack and large heap as long as you don't do so at the same time. Just keep in mind that there's only 2,048 bytes for both... – Adam Davis Jun 28 '12 at 15:35

The value __brkval is the sum of the .data variables, the .bss variables and the heap as can be seen in RAM memory map graphic at the bottom of this post. This will only change if you:

1. call malloc()
2. add more variables
3. add/increase strings in your code

freeRam() is essentially just telling you where __brkval is as offset from a variable placed on the stack. Since you aren't doing any of the above, __brkval is always at the same place. And since you are only calling freeRam() after the recursive functions return, the stack pointer is always at the same place. Hence, identical results.

To expand upon what @MikeJ-UK said, as you call a function, the stack pointer increases. As you exit a function, the stack unwinds and the stack pointer decreases. So, once a recursive function exits for the final time, the stack pointer will be back at where it was before the function was called. You will only be able to see the difference in stack pointer depth between recursion and tail recursion from inside the fuction.

So what you need to be doing is printing out the stack pointer from within the function before each recursive call. That should give you a better idea of what the difference between the two functions is.

In this forum thread Reply #18 has an interesting program to detect collisions between the stack pointer and the top of the heap. You may be able to use it to see that your heap isn't moving but your stack pointer is. But you will need to call the functions from withing the recursive routines to actually see the stack movement.