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:
- Skoki do C ++ Alex Allain , rozdz. 16: Recursion, str. 230
- 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.
