Recursion versus Tail Recursion on an Arduino
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) &amp;v - (__brkval == 0 ? (int) &amp;__heap_start : (int) __brkval);

  // Test to see if this measurement resulted in lower ram than we've seen before
  if(minimumRam &gt; 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.