Saturday 7 January 2017

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.



Answer



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.


No comments:

Post a Comment

arduino - Can I use TI's cc2541 BLE as micro controller to perform operations/ processing instead of ATmega328P AU to save cost?

I am using arduino pro mini (which contains Atmega328p AU ) along with cc2541(HM-10) to process and transfer data over BLE to smartphone. I...