Halo, Habr!
Hari ini kami melanjutkan penelitian kami pada pemrograman fungsional dalam konteks EcmaScript, spesifikasi yang didasarkan pada JavaScript. Dalam artikel siklus sebelumnya, topik berikut dipertimbangkan:
- Fungsi murni, lambda, kekebalan
- Komposisi, Kari, Aplikasi Sebagian
Rekursi
Seperti biasa, Wikipedia membantu kami menemukan definisi:
Rekursi - definisi, deskripsi, gambar dari suatu objek atau proses di dalam objek ini atau proses itu sendiri, yaitu situasi ketika objek tersebut merupakan bagian dari dirinya sendiri. Istilah "rekursi" digunakan dalam berbagai bidang pengetahuan khusus - dari linguistik hingga logika, tetapi menemukan aplikasi paling banyak dalam matematika dan ilmu komputer.
Untuk pemrograman, rekursi mengacu pada
proses yang melibatkan diri dalam tubuh mereka . Fungsi rekursif memiliki beberapa komponen wajib:
- Kondisi terminal - kondisi terminasi
- Aturan yang bergerak jauh ke rekursi
Perhatikan contoh rekursi - perhitungan faktorial yang paling populer.
const factorial = (n) => { if (n === 0) { return 1; } return n * factorial(n - 1); }
Kami membedakan komponen karakteristik dari fungsi rekursif. Kondisi terminal
if (n === 0) { return 1; }
dan aturan rekursi
return n * factorial(n - 1);
Penting untuk menyadari bahwa rekursi bukan fitur khusus JS, tetapi teknik yang sangat umum dalam pemrograman.
Proses rekursif dan berulang
Rekursi dapat diatur dalam dua cara: melalui proses rekursif atau melalui proses berulang.
Kami telah melihat proses rekursif:
const factorial = (n) => { if (n === 0) { return 1; } return n * factorial(n - 1); }
Solusi berulang untuk masalah faktorial akan terlihat seperti ini:
const factorial = (n) => { const iter = (counter, acc) => { if (counter === 1) { return acc; } return iter(counter - 1, counter * acc); }; return iter(n, 1); };
Kedua opsi ini bersifat rekursi. Kedua solusi memiliki fitur karakteristik rekursi: kondisi terminal dan aturan gerak sepanjang rekursi. Mari kita lihat perbedaan mereka.
Proses rekursif pada setiap langkah mengingat tindakan. yang perlu dilakukan. Setelah mencapai kondisi termal, ia melakukan semua tindakan yang diingat dalam urutan terbalik. Mari kita ilustrasikan dengan sebuah contoh. Ketika proses rekursif mempertimbangkan faktorial 6, maka ia perlu mengingat 5 angka untuk menghitungnya di bagian paling akhir, ketika Anda tidak bisa sampai di mana pun dan Anda tidak bisa bergerak lebih dalam lagi ke kedalaman. Ketika kita berada dalam panggilan fungsi berikutnya, di suatu tempat di luar panggilan ini, angka-angka yang diingat ini disimpan dalam memori.
Itu terlihat seperti ini:
factorial(3);
Seperti yang Anda lihat, ide dasar dari proses rekursif adalah untuk menunda perhitungan sampai akhir.
Proses seperti itu menghasilkan
keadaan yang
bervariasi waktu yang disimpan "di suatu tempat" di luar panggilan fungsi saat ini.
Saya pikir Anda ingat bahwa dalam artikel pertama dalam seri
Pemrograman Fungsional, kami berbicara tentang pentingnya kekebalan dan kurangnya negara. Memiliki kondisi menimbulkan banyak masalah yang tidak selalu mudah ditangani.
Proses berulang berbeda dari proses
rekursif dalam jumlah tetap negara. Pada setiap langkah, proses berulang mempertimbangkan segala sesuatu yang dapat dihitungnya, sehingga setiap langkah rekursi ada secara independen dari yang sebelumnya.
Ini terlihat seperti ini:
iter(3, 1);
Saya pikir jelas bahwa proses berulang memakan lebih sedikit memori. Karena itu, Anda harus selalu menggunakannya saat membuat rekursi. Satu-satunya pengecualian: jika kita tidak dapat menghitung nilai sampai kondisi termal tercapai.
Rekursi pohon
Banyak orang berpikir bahwa pohon dan bekerja dengan mereka adalah sesuatu yang sangat musykil, kompleks, dan tidak dapat dipahami oleh manusia biasa. Ini sebenarnya tidak demikian. Setiap struktur hierarkis dapat direpresentasikan dalam bentuk pohon. Bahkan pemikiran manusia seperti pohon.
Untuk lebih memahami rekursi pohon, mari kita lihat contoh sederhana dan populer - Angka Fibonacci.
Bilangan Fibonacci - elemen urutan numerik 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, ... (urutan A000045 dalam OEIS), di mana dua angka pertama adalah 1 dan 1, atau 0 dan 1, dan masing-masing angka berikutnya sama dengan jumlah dari dua angka sebelumnya. Dinamai setelah ahli matematika abad pertengahan Leonardo of Pisa (dikenal sebagai Fibonacci).
Secara matematis, cukup mudah untuk merumuskan deskripsi (dan pemrograman deklaratif adalah deskripsi) dari urutan ini:
fib(n) = [ 0 n = 0,//(1) 1 n = 1,//(2) fib(n-1) + fib(n-2) ]
Sekarang mari kita beralih dari matematika ke penalaran logis (setelah semua, kita perlu menulis logika program). Untuk menghitung fib (5), kita harus menghitung fib (4) dan fib (3). Untuk menghitung fib (4), kita harus menghitung fib (3) dan fib (2). Untuk menghitung fib (3), kita harus menghitung fib (2) dan seterusnya sampai kita mencapai nilai yang diketahui (1) dan (2) dalam model matematika kita.
Pikiran apa yang harus kita pikirkan untuk menuntun kita? Jelas, kita harus menggunakan rekursi. Kondisi termal dapat dirumuskan sebagai n <= 1. Namun, alih-alih satu cabang rekursi (seperti dalam contoh sebelumnya), kita akan memiliki dua cabang: fib (n-1), fib (n-2).
const fib = (n) => (n <= 1 ? n : fib(n - 1) + fib(n - 2));
Solusi ini memiliki minus yang signifikan! Ini mempertimbangkan hasil dari nilai yang sama n beberapa kali di cabang yang berbeda. Untuk mengatasi masalah ini, ada teknik pemrograman fungsional yang disebut
memoisasi , yang kita bicarakan di salah satu artikel berikut.
Kesimpulan
Rekursi adalah alat pemrograman yang sangat kuat. Biarkan saya mengingatkan Anda bahwa, sebagai aturan, kami menggunakan proses berulang. Layak untuk menggunakan proses rekursif hanya jika kita tidak dapat menghitung hasil antara pada setiap langkah rekursi.