Rumah > Artikel > pembangunan bahagian belakang > Bagaimana untuk menyelesaikan masalah limpahan timbunan fungsi rekursif C++?
Untuk masalah limpahan tindanan bagi fungsi rekursif C++, penyelesaiannya termasuk: mengurangkan kedalaman rekursi, mengurangkan saiz bingkai tindanan dan pengoptimuman rekursi ekor. Sebagai contoh, fungsi jujukan Fibonacci boleh mengelakkan limpahan tindanan melalui pengoptimuman rekursi ekor.
Fungsi rekursif mencipta bingkai tindanan baharu pada tindanan setiap kali ia dipanggil. Apabila kedalaman rekursi terlalu besar dan ruang tindanan tidak mencukupi, limpahan tindanan akan berlaku.
1. Kurangkan kedalaman rekursi
2. Kurangkan saiz bingkai tindanan
3. Pengoptimuman rekursif ekor
Pertimbangkan fungsi jujukan Fibonacci berikut:
// 尾递归版本 int fibonacci(int n) { return fibonacci_helper(n, 0, 1); } int fibonacci_helper(int n, int a, int b) { if (n == 0) return a; return fibonacci_helper(n-1, b, a+b); }
Ini ialah versi rekursif ekor kerana panggilan fungsi terakhir berulang terus ke dalam dirinya sendiri. Pengkompil akan mengoptimumkannya untuk mengelakkan limpahan tindanan.
Berikut ialah versi rekursif bukan ekor:
int fibonacci(int n) { if (n == 0) return 0; if (n == 1) return 1; return fibonacci(n-1) + fibonacci(n-2); }
Untuk versi rekursif bukan ekor ini, anda boleh menggunakan teknik pengoptimuman rekursif ekor untuk menukarnya menjadi versi rekursif ekor. Contohnya, menggunakan fungsi tambahan dan operasi swap:
int fibonacci(int n, int a = 0, int b = 1) { if (n == 0) return a; if (n == 1) return b; // 进行 swap 操作 std::swap(a, b); return fibonacci(n-1, b, a+b); }
Dengan menggunakan pengoptimuman rekursi ekor atau mengurangkan kedalaman rekursi, masalah limpahan tindanan fungsi rekursif dalam C++ boleh diselesaikan dengan berkesan.
Atas ialah kandungan terperinci Bagaimana untuk menyelesaikan masalah limpahan timbunan fungsi rekursif C++?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!