Electronic – arduino – Recursion versus Tail Recursion on an Arduino

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.

Best 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.

Related Topic