La placa Arduino Uno tiene RAM limitada, lo que significa que tiene una pila de llamadas limitada disponible. A veces, la recursión es la única opción rápida para implementar un cierto algoritmo. Entonces, dado que la pila de llamadas está severamente limitada, ¿cuál sería una manera de descubrir que dado un cierto programa que se ejecuta en el tablero, exactamente cuántas llamadas recursivas puede pagar antes de que se produzca un desbordamiento de la pila (y suceden cosas malas)?

Si realmente desea recurrir (y como @jippie dijo que es una mala idea; mensaje subliminal: no lo haga ) y desea saber cuánto puede repetir, entonces tendrá que realizar algunos cálculos y experimentos; Además, generalmente solo tendrá una aproximación, ya que depende mucho del estado de la memoria en el momento en que se llamará a su función recursiva.

Para esto, primero debe saber cómo se organiza SRAM dentro de Arduino basado en AVR (no se aplicará, por ejemplo, al Arduino Galileo de Intel). El siguiente diagrama de Adafruit lo muestra claramente:

Entonces necesita saber el tamaño total de su SRAM (depende de Atmel MCU, de ahí qué tipo de placa Arduino tiene).

En este diagrama, es fácil descubrir el tamaño del bloque de datos estáticos , ya que se conoce en tiempo de compilación y no cambiará más adelante.

El tamaño del montón puede ser más difícil de conocer ya que puede variar en tiempo de ejecución, dependiendo de las asignaciones de memoria dinámica ( malloco new) realizadas por su boceto o las bibliotecas que utiliza. Usar memoria dinámica es bastante raro en Arduino, pero algunas funciones estándar lo hacen (el tipo lo Stringusa, creo).

Para el tamaño de la pila , también variará durante el tiempo de ejecución, en función de la profundidad actual de las llamadas a funciones (cada llamada a la función toma 2 bytes en la pila para almacenar la dirección de la persona que llama) y el número y el tamaño de las variables locales, incluidos los argumentos pasados ​​( que también se almacenan en la Pila ) para todas las funciones llamadas hasta ahora.

Supongamos que su recurse()función usa 12 bytes para sus variables y argumentos locales, luego cada llamada a esta función (la primera de un llamador externo y las recursivas) usará 12+2bytes.

Si suponemos que:

• estás en Arduino UNO (SRAM = 2K)
• su boceto no usa asignación de memoria dinámica (sin montón )
• conoce el tamaño de sus datos estáticos (digamos 132 bytes)
• cuando recurse()se llama a su función desde su boceto, la pila actual tiene una longitud de 128 bytes

Luego te quedan 2048 - 132 - 128 = 1788bytes disponibles en la Pila . El número de llamadas recursivas a su función es 1788 / 14 = 127, por lo tanto , incluida la llamada inicial (que no es recursiva).

Como puede ver, esto es muy difícil, pero no imposible de encontrar lo que desea.

Una forma más simple de obtener el tamaño de pila disponible antes de recurse()llamar es utilizar la siguiente función (que se encuentra en el centro de aprendizaje Adafruit; no lo he probado yo mismo):

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

Le recomiendo que lea este artículo en el centro de aprendizaje Adafruit.

La recursión es una mala práctica en un microcontrolador, ya que usted ya lo dijo y probablemente quiera evitarlo siempre que sea posible. En el sitio de Arduino hay algunos ejemplos y bibliotecas disponibles para verificar el tamaño de RAM libre . Por ejemplo, puede usar esto para averiguar cuándo romper la recursividad o un poco más complicado / arriesgado para perfilar su boceto y codificar el límite en él. Este perfil sería necesario para cada cambio en su programa y para cada cambio en la cadena de herramientas Arduino.

Depende de la función.

Cada vez que se llama a una función, se empuja un nuevo marco a la pila. Por lo general, contendrá varios elementos críticos, que pueden incluir:

• Dirección de retorno (el punto en el código desde el que se llamó a la función).
• El puntero de instancia local ( this) si se llama a una función miembro.
• Parámetros pasados ​​a la función.
• Registre valores que deben restaurarse cuando finalice la función.
• Espacio para variables locales dentro de la función llamada.

Como puede ver, el espacio de pila requerido para una llamada determinada depende de la función. Por ejemplo, si escribe una función recursiva que solo toma un intparámetro y no utiliza variables locales, no necesitará mucho más que unos pocos bytes en la pila. Eso significa que puede llamarlo recursivamente mucho más que una función que toma varios parámetros y utiliza muchas variables locales (que consumirán la pila mucho más rápido).

Obviamente, el estado de la pila depende de qué más está sucediendo en el código. Si comienza una recursión directamente dentro de la loop()función estándar , entonces probablemente ya no habrá mucho en la pila. Sin embargo, si comienza anidando varios niveles en otras funciones, entonces no habrá tanto espacio. Eso afectará cuántas veces puede repetirse sin agotar la pila.

Vale la pena señalar que la optimización de recursión de cola existe en algunos compiladores (aunque no estoy seguro si avr-gcc lo admite). Si la llamada recursiva es lo último en una función, significa que a veces es posible evitar alterar el marco de la pila. El compilador puede simplemente reutilizar el marco existente, ya que la llamada 'padre' (por así decirlo) ha terminado de usarlo. Eso significará que, en teoría, puede seguir recurriendo tanto como desee, siempre que su función no llame a nada más.

Tenía exactamente la misma pregunta que cuando estaba leyendo Jumping into C ++ por Alex Allain , Ch 16: Recursion, p.230, así que realicé algunas pruebas.

TLDR;

Mi Arduino Nano (ATmega328 mcu) puede realizar 211 llamadas a funciones recursivas (para el código que se proporciona a continuación) antes de que se produzca un desbordamiento de pila y fallas.

En primer lugar, permítanme abordar esta afirmación:

A veces, la recursión es la única opción rápida para implementar un cierto algoritmo.

[Actualización: ah, leí la palabra "rápido". En ese caso tienes cierta validez. Sin embargo, creo que vale la pena decir lo siguiente.]

No, no creo que sea una afirmación verdadera. Estoy bastante seguro de que todos los algoritmos tienen una solución recursiva y no recursiva, sin excepción. Es solo que a veces es significativamente más fácilusar un algoritmo recursivo. Dicho esto, la recursión está muy mal vista para su uso en microcontroladores y probablemente nunca se permitirá en un código crítico para la seguridad. Sin embargo, es posible hacerlo en microcontroladores. Para saber qué tan "profundo" puede entrar en cualquier función recursiva, ¡solo pruébelo! Ejecútelo en su aplicación de la vida real en un caso de prueba de la vida real y elimine su condición base para que se repita infinitamente. Imprima un contador y vea por usted mismo cuán "profundo" puede llegar para saber si su algoritmo recursivo está empujando los límites de su RAM demasiado o no para ser usados ​​de manera práctica. Aquí hay un ejemplo a continuación para forzar el desbordamiento de la pila en un Arduino.

Ahora, algunas notas:

La cantidad de llamadas recursivas o "marcos de pila" que puede obtener está determinada por una serie de factores, que incluyen:

• El tamaño de tu RAM
• Cuántas cosas ya hay en tu pila o en tu montón (es decir: tu RAM libre es importante; free_RAM = total_RAM - stack_used - heap_usedo podrías decir free_RAM = stack_size_allocated - stack_size_used)
• El tamaño de cada nuevo "marco de pila" que se colocará en la pila para cada nueva llamada de función recursiva. Esto dependerá de la función que se llama y sus variables y requisitos de memoria, etc.

Mis resultados:

• 20171106-2054hrs - Toshiba Satellite con 16 GB de RAM; quad-core, Windows 8.1: valor final impreso antes del bloqueo: 43166
  • tardó varios segundos en bloquearse, ¿tal vez 5 ~ 10?
• 20180306-1913hrs Laptop Dell de alta gama con 64 GB de RAM; 8 núcleos, Linux Ubuntu 14.04 LTS: valor final impreso antes del bloqueo: 261752
  • seguido de la frase Segmentation fault (core dumped)
  • tomó solo ~ 4 ~ 5 segundos más o menos para bloquearse
• 20180306-1930hrs Arduino Nano: TBD --- está en ~ 250000 y sigue contando --- la configuración de optimización de Arduino debe haber causado que optimice la recursividad ... ??? Sí, ese es el caso.
  • Agregar #pragma GCC optimize ("-O0")al principio del archivo y rehacer:
• 20180307-0910hrs Arduino Nano: 32 kB flash, 2 kB SRAM, procesador de 16 MHz: valor final impreso antes del bloqueo: 211 Here are the final print results: 209 210 211 ⸮ 9⸮ 3⸮
  • tomó solo una fracción de segundo una vez que comenzó a imprimir a 115200 baudios en serie, quizás 1/10 seg.
  • 2 kiB = 2048 bytes / 211 cuadros de pila = 9.7 bytes / cuadro (suponiendo que TODA la RAM está siendo utilizada por la pila, lo que en realidad no es el caso), pero de todos modos esto parece muy razonable.

El código:

La aplicación para PC:

/*
stack_overflow
 - a quick program to force a stack overflow in order to see how many stack frames in a small function can be loaded onto the stack before the overflow occurs

By Gabriel Staples
www.ElectricRCAircraftGuy.com
Written: 6 Nov 2017
Updated: 6 Nov 2017

References:
 - Jumping into C++, by Alex Allain, pg. 230 - sample code here in the chapter on recursion

To compile and run:
Compile: g++ -Wall -std=c++11 stack_overflow_1.cpp -o stack_overflow_1
Run in Linux: ./stack_overflow_1
*/

#include <iostream>

void recurse(int count)
{
  std::cout << count << "\n";
  recurse(count + 1);
}

int main()
{
  recurse(1);
}

El programa "Sketch" de Arduino:

/*
recursion_until_stack_overflow
- do a quick recursion test to see how many times I can make the call before the stack overflows

Gabriel Staples
Written: 6 Mar. 2018 
Updated: 7 Mar. 2018 

References:
- Jumping Into C++, by Alex Allain, Ch. 16: Recursion, p.230
*/

// Force the compiler to NOT optimize! Otherwise this recursive function below just gets optimized into a count++ type
// incrementer instead of doing actual recursion with new frames on the stack each time. This is required since we are
// trying to force stack overflow. 
// - See here for all optimization levels: https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html
//   - They include: -O1, -O2, -O3, -O0, -Os (Arduino's default I believe), -Ofast, & -Og.

// I mention `#pragma GCC optimize` in my article here: http://www.electricrcaircraftguy.com/2014/01/the-power-of-arduino.html
#pragma GCC optimize ("-O0") 

void recurse(unsigned long count) // each call gets its own "count" variable in a new stack frame 
{
  // delay(1000);
  Serial.println(count);

  // It is not necessary to increment count since each function's variables are separate (so the count in each stack
  // frame will be initialized one greater than the last count)
  recurse (count + 1);

  // GS: notice that there is no base condition; ie: this recursive function, once called, will never finish and return!
}

void setup()
{
  Serial.begin(115200);
  Serial.println(F("\nbegin"));
  // First function call, so it starts at 1
  recurse (1);
}

void loop()
{
}

Referencias

1. Saltando a C ++ por Alex Allain , Ch 16: Recursion, p.230
2. http://www.electricrcaircraftguy.com/2014/01/the-power-of-arduino.html - literalmente: hice referencia a mi propio sitio web durante este "proyecto" para recordarme cómo cambiar los niveles de optimización del compilador Arduino para un archivo determinado con el #pragma GCC optimizecomando ya que sabía que lo tenía documentado allí.

Escribí este sencillo programa de prueba:

void setup() {
  // put your setup code here, to run once:
  Serial.begin(115200);
  recurse(1);
}

void loop() {
  // put your main code here, to run repeatedly: 

}

void recurse(long i) {
  Serial.println(i);
  recurse(i+1);
}

Lo compilé para el Uno, y mientras escribo, ¡ha recurrido más de 1 millón de veces! No lo sé, pero el compilador puede haber optimizado este programa.