Recursión versus Recursión de cola en un Arduino

En ambos casos, la función setup() está buscando una pérdida de memoria, pero no hay pérdida de memoria. Una función recursiva solo aumentará el uso de la pila cuando se produzca la recursión. Finalmente, la pila se desenrolla hasta que se ejecuta la instrucción final return , dejando la pila como estaba cuando se llamó por primera vez a la función, por lo que la memoria libre después de la llamada a la función es la misma que antes.

EDIT

Al principio pensé que su función freeMem verifica la cantidad de memoria asignada estáticamente. Adam Davis ha señalado que este no es el caso.

No conozco el Arduino o su entorno de desarrollo, pero el siguiente pseudocódigo podría ayudar. La idea general es determinar el uso de la pila justo antes de que se "desenrolle" ...

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;
}

Esto supone que la pila crece 'hacia abajo', y tendrás que mirar tu documentación para ver cómo hacer referencia a la parte superior de la pila ... Puedes usar tu función freeMem, pero en cualquier caso tendrás que restar el uso de la pila antes de llamar a setup() .

Una vez que la función vuelve a main, se devuelve la pila. La función no continúa utilizando la pila una vez que está terminada, por lo que medir la memoria después de que se realiza la función no le dirá nada. Debe medir la memoria cuando la recursión está en su punto más profundo.

Por ejemplo, puedes crear una variable que haga un seguimiento del mínimo de ram libre, y luego imprimirlo al final:

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);
}

La adición de una nueva variable global que realiza un seguimiento del ram mínimo que hemos visto, la actualiza cada vez que probamos el tamaño del ram, y la ejecución de esa prueba dentro de cada llamada de función garantiza que la probemos cada vez que cambia la pila. Luego imprimimos ese mínimo al final y puedes averiguar cuánta memoria quedaba cuando el sistema estaba en su mínimo.

El valor __brkval es la suma de las variables .data , las variables .bss y el montón como se puede ver en el gráfico del mapa de memoria RAM en la parte inferior de esta publicación . Esto solo cambiará si usted:

1. llamar a malloc()
2. agregar más variables
3. agregue / aumente cadenas en su código

freeRam() es esencialmente simplemente indicando dónde __brkval es un desplazamiento de una variable colocada en la pila. Como no estás haciendo nada de lo anterior, __brkval siempre está en el mismo lugar. Y dado que solo está llamando a freeRam() después de que regresen las funciones recursivas, el puntero de pila está siempre en el mismo lugar. Por lo tanto, resultados idénticos.

Para ampliar lo que dijo @ MikeJ-UK, al llamar a una función, el puntero de pila aumenta. Al salir de una función, la pila se desenrolla y el puntero de pila disminuye. Entonces, una vez que una función recursiva sale por última vez, el puntero de la pila volverá a estar donde estaba antes de que se llamara la función. Solo podrá ver la diferencia en la profundidad del puntero de pila entre la recursión y la recursión de la cola desde dentro de la función .

Entonces, lo que necesita hacer es imprimir el puntero de pila desde dentro de la función antes de cada llamada recursiva. Eso debería darle una mejor idea de cuál es la diferencia entre las dos funciones.

En este hilo del foro Reply # 18 tiene un programa interesante para detectar colisiones entre el puntero de pila y la parte superior del montón. Es posible que pueda usarlo para ver que su montón no se está moviendo, pero el puntero de su pila si lo está. Pero deberá llamar a las funciones desde las rutinas recursivas para ver realmente el movimiento de la pila.