Optimisasi rekursi ekor JavaScript

Halo pembaca.

Kadang-kadang untuk menyelesaikan masalah Anda harus menggunakan Rekursi , yang memiliki pro dan kontra. Saya mengalami masalah stack overflow.

Kedalaman rekursi maksimum dibatasi oleh mesin JavaScript. Anda dapat menghitung secara akurat 10.000 panggilan bersarang, beberapa penerjemah mengizinkan lebih, tetapi untuk sebagian besar dari mereka 100.000 panggilan berada di luar jangkauan kemampuan. Ada optimasi otomatis yang membantu menghindari meluapnya tumpukan panggilan ("optimisasi rekursi ekor"), tetapi belum didukung di mana-mana dan hanya berfungsi untuk kasus sederhana.

Contoh fungsi rekursif:

function sum(n) { return n === 0 ? 0 : n + sum(n - 1) } sum(5) // 1 + 2 + 3 + 4 + 5 = 15 sum(100000) // Error: Maximum call stack size exceeded. 

Tail recursion memungkinkan optimalisasi panggilan oleh kompiler dan sudah dalam standar ES6 , tetapi dukungan browser menyisakan banyak yang diinginkan .

Contoh fungsi rekursif ekor:

 function sum(number, s = 0){ return number === 0 ? s : sum(number - 1, s + number) } 

Tapi, tanpa dukungan browser, kita akan menghadapi masalah yang sama - stack overflow. Kita bisa mencoba menggunakannya bersama dengan Trampolining .

Kami akan menulis dekorator yang akan mengambil fungsi rekursif yang dimodifikasi (langkah berikutnya) dan menjalankannya dalam satu lingkaran, tanpa meningkatkan kedalaman panggilan.

 function trampoline(fn) { return function(...args) { let result = fn.apply(fn.context, args) while (typeof result === 'function') { result = result() } return result } } 

Sekarang fungsi rekursif kami harus mengembalikan fungsi yang akan segera dieksekusi oleh dekorator. Dengan cara ini, kita secara kondisional akan membuat berbagai fungsi dan menjalankannya secara bergantian. Tetapi karena kita mengembalikan fungsi anonim baru setiap kali, kode ini akan bekerja sedikit lebih lambat.

 function sum(number, s = 0) { return number === 0 ? s : () => sum(number - 1, s + number) } 

Kami menggunakan:

 const trampolineSum = trampoline(sum) trampolineSum(100000) // 5000050000 

Ini artikel pertama saya. Saya mencoba untuk tidak menceritakan kembali konsep dan memberikan tautan ke sumber. Topiknya tidak unik dan sudah lama ada di situs berbahasa Inggris, sayangnya saya tidak menemukannya dalam bahasa Rusia.

Terima kasih atas perhatian anda Semoga harimu menyenangkan :)

Perbarui
Kinerja:

Rekursi # 1




Iterasi # 2




# 3 Ekor rekursi dan trampolin




# 4 Ekor rekursi dan trampolin (dalam jumlah besar)




Menurut hasil, kami melihat bahwa dekorator kami, meskipun memungkinkan kami untuk menghindari kesalahan stack overflow, tetapi bekerja lebih lambat daripada versi rekursif dan berulang. Jadi metode ini harus digunakan hanya jika Anda tidak dapat mengganti rekursi dengan iterasi atau takut tumpukan berlebih saat menjalankan fungsi rekursif Anda.