Płyta Arduino Uno ma ograniczoną pamięć RAM, co oznacza, że ​​ma ograniczony stos połączeń. Czasami rekurencja jest jedyną szybką opcją do implementacji określonego algorytmu. Więc biorąc pod uwagę, że stos wywołań jest poważnie ograniczony, jaki byłby sposób, aby dowiedzieć się, że biorąc pod uwagę pewien program działający na płycie, ile dokładnie wywołań rekurencyjnych możesz sobie pozwolić, zanim nastąpi przepełnienie stosu (i zdarzają się złe rzeczy)?

Jeśli naprawdę chcesz się powtórzyć (i jak powiedział @jippie, to zły pomysł; wiadomość podprogowa: nie rób tego ) i chcesz wiedzieć, ile możesz powtórzyć, będziesz musiał wykonać pewne obliczenia i eksperymenty; również na ogół będzie to tylko przybliżenie, ponieważ zależy ono w dużej mierze od stanu pamięci w momencie wywołania funkcji rekurencyjnej.

W tym celu najpierw powinieneś wiedzieć, jak SRAM jest zorganizowany w Arduino opartym na AVR (nie będzie to dotyczyło np. Arduino Galileo firmy Intel). Poniższy schemat z Adafruit pokazuje to wyraźnie:

Następnie musisz znać całkowity rozmiar SRAM (zależy od MCU Atmela, stąd jaki rodzaj płyty Arduino posiadasz).

Na tym diagramie łatwo jest ustalić rozmiar bloku danych statycznych, jaki jest znany w czasie kompilacji i nie zmieni się później.

Rozmiar sterty może być trudniejszy do ustalenia, ponieważ może się różnić w czasie wykonywania, w zależności od dynamicznych przydziałów pamięci ( malloclub new) wykonywanych przez szkic lub używane biblioteki. Używanie pamięci dynamicznej jest dość rzadkie w Arduino, ale robią to niektóre standardowe funkcje ( Stringmyślę, że używa tego typu ).

W przypadku rozmiaru stosu będzie się on również zmieniać w czasie wykonywania, w zależności od bieżącej głębokości wywołań funkcji (każde wywołanie funkcji zajmuje 2 bajty na stosie do przechowywania adresu wywołującego) oraz liczby i wielkości zmiennych lokalnych, w tym przekazanych argumentów ( które są również przechowywane na stosie ) dla wszystkich wywoływanych do tej pory funkcji.

Załóżmy więc, że twoja recurse()funkcja używa 12 bajtów dla swoich lokalnych zmiennych i argumentów, a następnie każde wywołanie tej funkcji (pierwsze wywołanie zewnętrzne i rekurencyjne) użyje 12+2bajtów.

Jeśli przypuszczamy, że:

• jesteś na Arduino UNO (SRAM = 2K)
• twój szkic nie korzysta z dynamicznej alokacji pamięci (bez sterty )
• znasz rozmiar swoich danych statycznych (powiedzmy 132 bajty)
• kiedy twoja recurse()funkcja jest wywoływana ze szkicu, bieżący stos ma 128 bajtów długości

Pozostają ci 2048 - 132 - 128 = 1788dostępne bajty na stosie . Dlatego liczba wywołań rekurencyjnych do Twojej funkcji 1788 / 14 = 127, w tym wywołanie początkowe (które nie jest rekurencyjne).

Jak widać, znalezienie tego, czego chcesz, jest bardzo trudne, ale nie niemożliwe.

Prostszym sposobem na uzyskanie dostępnego wcześniej rozmiaru stosu recurse()byłoby użycie następującej funkcji (znalezionej w centrum szkoleniowym Adafruit; sam tego nie testowałem):

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

Gorąco zachęcam do przeczytania tego artykułu w centrum szkoleniowym Adafruit.

Rekurencja jest złą praktyką na mikrokontrolerze, ponieważ sam już to powiedziałeś i prawdopodobnie chcesz tego uniknąć, gdy tylko jest to możliwe. Na stronie Arduino jest kilka przykładów i bibliotek dostępnych do sprawdzania wielkości wolnej pamięci RAM . Możesz na przykład użyć tego, aby dowiedzieć się, kiedy przerwać rekurencję lub nieco trudniej / ryzykować, aby profilować swój szkic i nałożyć na niego sztywny kod. Ten profil byłby wymagany przy każdej zmianie w twoim programie i każdej zmianie w łańcuchu narzędzi Arduino.

To zależy od funkcji.

Za każdym razem, gdy wywoływana jest funkcja, nowa ramka jest wypychana na stos. Zwykle będzie zawierać różne krytyczne elementy, w tym potencjalnie:

• Adres zwrotny (punkt w kodzie, z którego wywołano funkcję).
• Lokalny wskaźnik instancji ( this) w przypadku wywołania funkcji członka.
• Parametry przekazane do funkcji.
• Zarejestruj wartości, które należy przywrócić po zakończeniu funkcji.
• Miejsce na zmienne lokalne w wywoływanej funkcji.

Jak widać, przestrzeń stosu wymagana dla danego wywołania zależy od funkcji. Na przykład, jeśli napiszesz funkcję rekurencyjną, która bierze tylko intparametr i nie używa zmiennych lokalnych, nie będzie potrzebować więcej niż kilku bajtów na stosie. Oznacza to, że możesz rekurencyjnie nazywać to znacznie więcej niż funkcją, która bierze kilka parametrów i używa wielu lokalnych zmiennych (które pochłaniają stos znacznie szybciej).

Oczywiście stan stosu zależy od tego, co dzieje się w kodzie. Jeśli rozpoczniesz rekurencję bezpośrednio w loop()funkcji standardowej , prawdopodobnie na stosie nie będzie już dużo. Jeśli jednak zaczniesz, zagnieżdżony kilka poziomów głęboko w innych funkcjach, nie będzie już tyle miejsca. Wpłynie to na liczbę powtórzeń bez wyczerpania stosu.

Warto zauważyć, że optymalizacja rekurencji ogona istnieje w niektórych kompilatorach (chociaż nie jestem pewien, czy avr-gcc to obsługuje). Jeśli wywołanie rekurencyjne jest ostatnią rzeczą w funkcji, oznacza to, że czasami można w ogóle uniknąć zmiany ramki stosu. Kompilator może po prostu ponownie wykorzystać istniejącą ramkę, ponieważ wywołanie „rodzicielskie” (że tak powiem) zostało z niego zakończone. Oznacza to, że możesz teoretycznie kontynuować rekurencję tak długo, jak chcesz, o ile twoja funkcja nie wywołuje niczego innego.

Miałem dokładnie to samo pytanie, co podczas czytania Jumping into C ++ autorstwa Alexa Allaina , Ch 16: Recursion, str. 230, więc przeprowadziłem kilka testów.

TLDR;

Mój Arduino Nano (ATmega328 mcu) może wykonywać 211 wywołań funkcji rekurencyjnych (dla kodu podanego poniżej), zanim przepełni się stos i zawiesi.

Po pierwsze, pozwól mi zająć się tym roszczeniem:

Czasami rekurencja jest jedyną szybką opcją do implementacji określonego algorytmu.

[Aktualizacja: ah, przejrzałem słowo „szybki”. W takim przypadku masz pewną ważność. Niemniej jednak uważam, że warto powiedzieć, co następuje.]

Nie, nie sądzę, żeby to było prawdziwe stwierdzenie. Jestem pewien, że wszystkie algorytmy mają zarówno rekurencyjne, jak i nierekurencyjne rozwiązanie, bez wyjątku. Po prostu czasami jest to znacznie łatwiejszeużyć algorytmu rekurencyjnego. Powiedziawszy to, rekursja jest bardzo niezadowolona z zastosowania w mikrokontrolerach i prawdopodobnie nigdy nie będzie dozwolona w kodzie krytycznym dla bezpieczeństwa. Niemniej jednak można to oczywiście zrobić na mikrokontrolerach. Aby wiedzieć, jak „głęboki” możesz przejść do dowolnej funkcji rekurencyjnej, po prostu ją przetestuj! Uruchom go w swojej rzeczywistej aplikacji w prawdziwym przypadku testowym i usuń podstawowy warunek, aby nieskończenie powrócił. Wydrukuj licznik i przekonaj się, jak „głęboki” możesz przejść, abyś wiedział, czy Twój algorytm rekurencyjny przesuwa granice pamięci RAM zbyt blisko, aby można go było praktycznie wykorzystać. Oto przykład poniżej, aby wymusić przepełnienie stosu na Arduino.

Teraz kilka notatek:

Liczba wywołań rekurencyjnych lub „ramek stosu”, które można uzyskać, zależy od wielu czynników, w tym:

• Rozmiar twojej pamięci RAM
• Ile rzeczy jest już na twoim stosie lub zostało zebranych na stosie (tj .: liczy się twoja wolna pamięć RAM; free_RAM = total_RAM - stack_used - heap_usedlub możesz powiedzieć free_RAM = stack_size_allocated - stack_size_used)
• Rozmiar każdej nowej „ramki stosu”, która zostanie umieszczona na stosie dla każdego nowego wywołania funkcji rekurencyjnej. Będzie to zależeć od wywołanej funkcji, jej zmiennych i wymagań dotyczących pamięci itp.

Moje wyniki:

• 20171106-2054hrs - Toshiba Satellite z 16 GB pamięci RAM; czterordzeniowy, Windows 8.1: wartość końcowa wydrukowana przed awarią: 43166
  • rozbicie się zajęło kilka sekund - może 5 ~ 10?
• 20180306-1913hrs Wysokiej klasy laptop Dell z 64 GB pamięci RAM; 8-rdzeniowy, Linux Ubuntu 14.04 LTS: końcowa wartość wydrukowana przed awarią: 261752
  • po którym następuje fraza Segmentation fault (core dumped)
  • awaria trwała tylko ~ 4 ~ 5 sekund
• 20180306-1930hrs Arduino Nano: TBD --- jest na ~ 250000 i wciąż się liczy --- ustawienia optymalizacji Arduino musiały spowodować optymalizację rekurencji ... ??? Tak jest w tym przypadku.
  • Dodaj #pragma GCC optimize ("-O0")na górę pliku i wykonaj ponownie:
• 20180307-0910 godz. Arduino Nano: pamięć flash 32 kB, pamięć SRAM 2 kB, procesor 16 MHz: wartość końcowa wydrukowana przed awarią: 211 Here are the final print results: 209 210 211 ⸮ 9⸮ 3⸮
  • zajęło tylko ułamek sekundy, kiedy zaczęło drukować z szybkością szeregową 115200 bodów - może 1/10 sekundy
  • 2 kiB = 2048 bajtów / 211 ramek stosu = 9,7 bajtów / ramkę (zakładając, że stos zajmuje całą pamięć RAM - co tak naprawdę nie jest) - ale wydaje się to jednak bardzo rozsądne.

Kod:

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

Program Arduino „Sketch”:

/*
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()
{
}

Bibliografia:

1. Skoki do C ++ Alex Allain , rozdz. 16: Recursion, str. 230
2. http://www.electricrcaircraftguy.com/2014/01/the-power-of-arduino.html - dosłownie: podczas tego „projektu” odwołałem się do własnej strony internetowej, aby przypomnieć sobie, jak zmienić poziomy optymalizacji kompilatora Arduino dla danego pliku z #pragma GCC optimizerozkazem, ponieważ wiedziałem, że go tam udokumentowałem.

Napisałem ten prosty program testowy:

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

Skompilowałem go dla Uno i jak piszę, powrócił ponad milion razy! Nie wiem, ale kompilator mógł zoptymalizować ten program