Papan Arduino Uno memiliki RAM terbatas yang berarti memiliki tumpukan panggilan terbatas. Terkadang, rekursi adalah satu-satunya pilihan cepat untuk mengimplementasikan algoritma tertentu. Jadi, mengingat bahwa tumpukan panggilan sangat terbatas, apa yang akan menjadi cara untuk mengetahui bahwa mengingat program tertentu berjalan di papan tulis, persis berapa banyak panggilan rekursif yang Anda mampu sebelum ada tumpukan melimpah (dan hal-hal buruk terjadi)?

Jika Anda benar-benar ingin muncul kembali (dan seperti yang dikatakan @jippie itu adalah ide yang buruk; pesan bawah sadar: jangan lakukan itu ) dan ingin tahu seberapa banyak Anda dapat berulang, maka Anda harus melakukan beberapa perhitungan dan percobaan; Anda juga biasanya hanya akan memiliki perkiraan karena tergantung banyak pada kondisi memori pada saat fungsi rekursif Anda akan dipanggil.

Untuk ini, Anda harus terlebih dahulu tahu bagaimana SRAM diatur dalam Arduino berbasis AVR (itu tidak akan berlaku untuk misalnya Arduino Galileo oleh Intel). Diagram berikut dari Adafruit menunjukkannya dengan jelas:

Maka Anda perlu mengetahui ukuran total SRAM Anda (tergantung pada Atmel MCU, maka jenis papan Arduino yang Anda miliki).

Pada diagram ini, mudah untuk mengetahui ukuran blok Data Statis seperti yang diketahui pada waktu kompilasi dan tidak akan berubah nanti.

The Heap Ukuran dapat lebih sulit untuk mengetahui karena dapat bervariasi pada saat runtime, tergantung pada alokasi memori dinamis ( mallocatau new) dilakukan oleh sketsa atau perpustakaan menggunakan. Menggunakan memori dinamis sangat jarang di Arduino, tetapi beberapa fungsi standar melakukannya ( Stringsaya pikir itu menggunakan tipe itu).

Untuk ukuran Stack , ini juga akan bervariasi selama runtime, berdasarkan pada kedalaman panggilan fungsi saat ini (setiap panggilan fungsi membutuhkan 2 byte pada Stack untuk menyimpan alamat pemanggil) dan jumlah dan ukuran variabel lokal termasuk argumen yang diteruskan ( yang juga disimpan di Stack ) untuk semua fungsi yang dipanggil sampai sekarang.

Jadi anggaplah recurse()fungsi Anda menggunakan 12 byte untuk variabel dan argumen lokalnya, maka setiap panggilan ke fungsi ini (yang pertama dari penelepon eksternal dan yang rekursif) akan menggunakan 12+2byte.

Jika kita mengira bahwa:

• Anda berada di Arduino UNO (SRAM = 2K)
• sketsa Anda tidak menggunakan alokasi memori dinamis (tidak ada tumpukan )
• Anda tahu ukuran Data Statis Anda (katakanlah 132 byte)
• ketika recurse()fungsi Anda dipanggil dari sketsa Anda, tumpukan saat ini adalah 128 byte

Kemudian Anda dibiarkan dengan 2048 - 132 - 128 = 1788byte yang tersedia di Stack . Dengan demikian, jumlah panggilan rekursif ke fungsi Anda 1788 / 14 = 127, termasuk panggilan awal (yang bukan merupakan panggilan rekursif).

Seperti yang Anda lihat, ini sangat sulit, tetapi bukan tidak mungkin untuk menemukan apa yang Anda inginkan.

Cara yang lebih sederhana untuk mendapatkan ukuran tumpukan tersedia sebelum recurse()dipanggil adalah dengan menggunakan fungsi berikut (ditemukan di pusat pembelajaran Adafruit; saya belum mengujinya sendiri):

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

Saya sangat menyarankan Anda untuk membaca artikel ini di pusat pembelajaran Adafruit.

Rekursi adalah praktik buruk pada mikrokontroler karena Anda telah menyatakan diri Anda dan Anda mungkin ingin menghindarinya kapan pun memungkinkan. Di situs Arduino ada beberapa contoh dan perpustakaan yang tersedia untuk memeriksa ukuran RAM gratis . Misalnya Anda dapat menggunakan ini untuk mencari tahu kapan harus istirahat rekursi atau sedikit rumit / berisiko untuk profil sketsa Anda dan kode keras batas di dalamnya. Profil ini diperlukan untuk setiap perubahan dalam program Anda dan untuk setiap perubahan dalam rantai alat Arduino.

Tergantung fungsinya.

Setiap kali fungsi dipanggil, bingkai baru didorong ke tumpukan. Biasanya akan berisi berbagai item penting, berpotensi termasuk:

• Alamat pengirim (titik pada kode dari mana fungsi dipanggil).
• Pointer instance lokal ( this) jika memanggil fungsi anggota.
• Parameter masuk ke fungsi.
• Daftarkan nilai yang perlu dipulihkan saat fungsi berakhir.
• Ruang untuk variabel lokal di dalam fungsi yang dipanggil.

Seperti yang Anda lihat, ruang tumpukan yang diperlukan untuk panggilan yang diberikan tergantung pada fungsinya. Misalnya, jika Anda menulis fungsi rekursif yang hanya mengambil intparameter dan tidak menggunakan variabel lokal, itu tidak akan membutuhkan lebih dari beberapa byte pada stack. Itu berarti Anda dapat menyebutnya secara rekursif lebih dari fungsi yang mengambil beberapa parameter dan menggunakan banyak variabel lokal (yang akan memakan tumpukan lebih cepat).

Jelas keadaan tumpukan tergantung pada apa lagi yang terjadi dalam kode. Jika Anda memulai rekursi langsung di dalam loop()fungsi standar , maka kemungkinan tidak akan ada banyak pada stack. Namun, jika Anda memulainya bersarang beberapa level dalam fungsi lain, maka tidak akan ada banyak ruang. Itu akan mempengaruhi berapa kali Anda bisa kambuh tanpa menguras tumpukan.

Perlu dicatat bahwa optimasi rekursi ekor ada pada beberapa kompiler (walaupun saya tidak yakin apakah avr-gcc mendukungnya). Jika panggilan rekursif adalah hal terakhir dalam suatu fungsi, itu berarti kadang-kadang mungkin untuk menghindari mengubah bingkai tumpukan sama sekali. Compiler hanya dapat menggunakan kembali bingkai yang ada, karena panggilan 'induk' (jadi untuk berbicara) selesai menggunakannya. Itu berarti Anda secara teoritis dapat terus berulang sebanyak yang Anda suka, selama fungsi Anda tidak memanggil yang lain.

Saya memiliki pertanyaan yang sama persis seperti saya membaca Jumping into C ++ oleh Alex Allain , Bab 16: Rekursi, hal.230, jadi saya menjalankan beberapa tes.

TLDR;

Arduino Nano saya (ATmega328 mcu) dapat melakukan 211 panggilan fungsi rekursif (untuk kode yang diberikan di bawah ini) sebelum memiliki stack overflow dan crash.

Pertama, izinkan saya menangani klaim ini:

Terkadang, rekursi adalah satu-satunya pilihan cepat untuk mengimplementasikan algoritma tertentu.

[Pembaruan: ah, saya membaca sepintas kata "cepat". Dalam hal ini Anda memiliki validitas. Namun demikian, saya pikir ada baiknya mengatakan hal berikut.]

Tidak, saya tidak berpikir itu pernyataan yang benar. Saya cukup yakin semua algoritma memiliki solusi rekursif dan non-rekursif, tanpa kecuali. Hanya saja kadang-kadang jauh lebih mudahuntuk menggunakan algoritma rekursif. Karena itu, rekursi sangat disukai untuk digunakan pada mikrokontroler dan mungkin tidak akan pernah diizinkan dalam kode keamanan kritis. Meskipun demikian, tentu saja dimungkinkan untuk melakukannya pada mikrokontroler. Untuk mengetahui seberapa "dalam" Anda bisa masuk ke fungsi rekursif yang diberikan, cukup mengujinya! Jalankan dalam aplikasi kehidupan nyata Anda dalam test case kehidupan nyata, dan lepaskan kondisi dasar Anda sehingga akan terulang kembali. Cetak penghitung dan lihat sendiri seberapa "dalam" Anda sehingga Anda tahu apakah algoritma rekursif Anda mendorong batas RAM Anda terlalu dekat untuk digunakan secara praktis. Berikut adalah contoh di bawah ini untuk memaksa stack overflow pada Arduino.

Sekarang, beberapa catatan:

Berapa banyak panggilan rekursif, atau "stack frames" yang bisa Anda dapatkan ditentukan oleh sejumlah faktor, termasuk:

• Ukuran RAM Anda
• Berapa banyak barang yang sudah ada di tumpukan Anda atau diambil di tumpukan Anda (yaitu: RAM Anda penting;, free_RAM = total_RAM - stack_used - heap_usedatau Anda mungkin mengatakan free_RAM = stack_size_allocated - stack_size_used)
• Ukuran setiap "stack frame" baru yang akan ditempatkan ke stack untuk setiap panggilan fungsi rekursif baru. Ini akan tergantung pada fungsi yang dipanggil dan variabel dan persyaratan memori, dll.

Hasil saya:

• 20171106-2054hrs - Toshiba Satellite dengan 16 GB RAM; quad-core, Windows 8.1: nilai akhir yang dicetak sebelum crash: 43166
  • butuh beberapa detik untuk crash - mungkin 5 ~ 10?
• 20180306-1913hrs Laptop high-end Dell dengan RAM 64 GB; 8-core, Linux Ubuntu 14.04 LTS: nilai akhir dicetak sebelum crash: 261752
  • diikuti oleh frasa Segmentation fault (core dumped)
  • hanya butuh ~ 4 ~ 5 detik untuk crash
• 20180306-1930hrs Arduino Nano: TBD --- ada di ~ 250000 dan masih menghitung --- pengaturan optimasi Arduino pasti menyebabkannya mengoptimalkan rekursi ... ??? Ya itu masalahnya.
  • Tambahkan #pragma GCC optimize ("-O0")ke bagian atas file dan ulangi:
• 20180307-0910hrs Arduino Nano: 32 kB flash, 2 kB SRAM, proses 16 MHz atau lebih: nilai akhir dicetak sebelum mogok: 211 Here are the final print results: 209 210 211 ⸮ 9⸮ 3⸮
  • hanya membutuhkan sepersekian detik setelah mulai mencetak pada 115200 serial baud-rate - mungkin 1/10 detik
  • 2 kiB = 2048 bytes / 211 stack frames = 9,7 bytes / frame (dengan asumsi SEMUA RAM Anda sedang digunakan oleh stack - yang sebenarnya tidak demikian) - tetapi ini tampaknya masih sangat masuk akal.

Kode:

Aplikasi 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 "Sketsa" 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()
{
}

Referensi:

1. Jumping into C ++ oleh Alex Allain , Bab 16: Rekursi, hal.230
2. http://www.electricrcaircraftguy.com/2014/01/the-power-of-arduino.html - secara harfiah: Saya mereferensikan situs web saya sendiri selama "proyek" ini untuk mengingatkan diri saya bagaimana mengubah tingkat optimisasi kompilator Arduino untuk file yang diberikan dengan #pragma GCC optimizeperintah karena saya tahu saya sudah didokumentasikan di sana.

Saya menulis program tes sederhana ini:

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

Saya mengkompilasinya untuk Uno, dan ketika saya menulisnya telah berulang lebih dari 1 juta kali! Saya tidak tahu, tetapi kompiler mungkin telah mengoptimalkan program ini