Mari kembali ke fungsi dan mempelajarinya lebih dalam.
Topik pertama kita adalah rekursi .
Jika Anda bukan orang baru dalam pemrograman, mungkin sudah familiar dan Anda dapat melewati bab ini.
Rekursi adalah pola pemrograman yang berguna dalam situasi ketika suatu tugas dapat secara alami dipecah menjadi beberapa tugas yang sejenis, namun lebih sederhana. Atau ketika suatu tugas dapat disederhanakan menjadi tindakan yang mudah ditambah varian yang lebih sederhana dari tugas yang sama. Atau, seperti yang akan segera kita lihat, menangani struktur data tertentu.
Ketika suatu fungsi menyelesaikan suatu tugas, dalam prosesnya ia dapat memanggil banyak fungsi lainnya. Sebagian kasusnya adalah ketika suatu fungsi memanggil dirinya sendiri . Itu disebut rekursi .
Untuk memulai sesuatu yang sederhana – mari kita tuliskan fungsi pow(x, n) yang menaikkan x ke pangkat alami n . Dengan kata lain, mengalikan x dengan dirinya sendiri n kali.
kekuatan(2, 2) = 4 kekuatan(2, 3) = 8 kekuatan(2, 4) = 16
Ada dua cara untuk menerapkannya.
Pemikiran berulang: perulangan for :
fungsi daya(x, n) {
misalkan hasilnya = 1;
// mengalikan hasilnya dengan x n kali dalam perulangan
untuk (misalkan i = 0; i < n; i++) {
hasil *= x;
}
hasil pengembalian;
}
peringatan( kekuatan(2, 3) ); // 8Pemikiran rekursif: sederhanakan tugas dan panggil self:
fungsi daya(x, n) {
jika (n == 1) {
kembalikan x;
} kalau tidak {
kembalikan x * kekuatan(x, n - 1);
}
}
peringatan( kekuatan(2, 3) ); // 8Harap perhatikan bagaimana varian rekursif berbeda secara mendasar.
Ketika pow(x, n) dipanggil, eksekusi dibagi menjadi dua cabang:
jika n==1 = x
/
kekuatan(x, n) =
lain = x * kekuatan(x, n - 1) Jika n == 1 , maka semuanya sepele. Ini disebut basis rekursi, karena langsung menghasilkan hasil yang jelas: pow(x, 1) sama dengan x .
Jika tidak, kita dapat menyatakan pow(x, n) sebagai x * pow(x, n - 1) . Dalam matematika, seseorang akan menulis x n = x * x n-1 . Ini disebut langkah rekursif : kita mengubah tugas menjadi tindakan yang lebih sederhana (perkalian dengan x ) dan pemanggilan tugas yang sama yang lebih sederhana ( pow dengan n yang lebih rendah). Langkah selanjutnya menyederhanakannya lebih jauh hingga n mencapai 1 .
Kita juga dapat mengatakan bahwa pow memanggil dirinya sendiri secara rekursif hingga n == 1 .
Misalnya, untuk menghitung pow(2, 4) varian rekursif melakukan langkah-langkah berikut:
pow(2, 4) = 2 * pow(2, 3)
pow(2, 3) = 2 * pow(2, 2)
pow(2, 2) = 2 * pow(2, 1)
pow(2, 1) = 2
Jadi, rekursi mengurangi pemanggilan fungsi menjadi lebih sederhana, dan kemudian – menjadi lebih sederhana, dan seterusnya, hingga hasilnya menjadi jelas.
Rekursi biasanya lebih singkat
Solusi rekursif biasanya lebih pendek dibandingkan solusi iteratif.
Di sini kita dapat menulis ulang hal yang sama menggunakan operator kondisional ? daripada if membuat pow(x, n) lebih singkat dan masih mudah dibaca:
fungsi daya(x, n) {
kembali (n == 1) ? x : (x * kekuatan(x, n - 1));
} Jumlah maksimal panggilan bersarang (termasuk yang pertama) disebut kedalaman rekursi . Dalam kasus kami, itu akan menjadi persis n .
Kedalaman rekursi maksimal dibatasi oleh mesin JavaScript. Kita dapat mengandalkannya menjadi 10.000, beberapa mesin mengizinkan lebih banyak, tetapi 100.000 mungkin di luar batas bagi sebagian besar mesin. Ada pengoptimalan otomatis yang membantu meringankan hal ini (“pengoptimalan panggilan ekor”), namun pengoptimalan tersebut belum didukung di semua tempat dan hanya berfungsi dalam kasus sederhana.
Hal ini membatasi penerapan rekursi, namun masih sangat luas. Ada banyak tugas di mana cara berpikir rekursif memberikan kode yang lebih sederhana dan lebih mudah dipelihara.
Sekarang mari kita periksa cara kerja panggilan rekursif. Untuk itu kita akan melihat di balik terpal fungsi.
Informasi tentang proses eksekusi fungsi yang sedang berjalan disimpan dalam konteks eksekusinya .
Konteks eksekusi adalah struktur data internal yang berisi detail tentang eksekusi suatu fungsi: lokasi aliran kontrol sekarang, variabel saat ini, nilai this (kami tidak menggunakannya di sini) dan beberapa detail internal lainnya.
Satu pemanggilan fungsi memiliki tepat satu konteks eksekusi yang terkait dengannya.
Saat suatu fungsi melakukan panggilan bertingkat, hal berikut akan terjadi:
Fungsi saat ini dijeda.
Konteks eksekusi yang terkait dengannya diingat dalam struktur data khusus yang disebut tumpukan konteks eksekusi .
Panggilan bersarang dijalankan.
Setelah berakhir, konteks eksekusi lama diambil dari tumpukan, dan fungsi luar dilanjutkan dari tempatnya berhenti.
Mari kita lihat apa yang terjadi selama panggilan pow(2, 3) .
Di awal panggilan pow(2, 3) konteks eksekusi akan menyimpan variabel: x = 2, n = 3 , alur eksekusi ada di baris 1 fungsi.
Kita dapat membuat sketsanya sebagai:
Konteks: { x: 2, n: 3, pada baris 1 } pow(2, 3)
Saat itulah fungsi mulai dijalankan. Kondisi n == 1 salah, sehingga aliran berlanjut ke cabang kedua if :
fungsi daya(x, n) {
jika (n == 1) {
kembalikan x;
} kalau tidak {
kembalikan x * kekuatan(x, n - 1);
}
}
peringatan( kekuatan(2, 3) );Variabelnya sama, tetapi garisnya berubah, jadi konteksnya sekarang:
Konteks: { x: 2, n: 3, pada baris 5 } pow(2, 3)
Untuk menghitung x * pow(x, n - 1) , kita perlu membuat subpanggilan pow dengan argumen baru pow(2, 2) .
Untuk melakukan panggilan bersarang, JavaScript mengingat konteks eksekusi saat ini dalam tumpukan konteks eksekusi .
Di sini kita memanggil fungsi yang sama pow , tetapi itu tidak masalah. Prosesnya sama untuk semua fungsi:
Konteks saat ini “diingat” di atas tumpukan.
Konteks baru dibuat untuk subpanggilan.
Ketika subpanggilan selesai – konteks sebelumnya dikeluarkan dari tumpukan, dan eksekusinya dilanjutkan.
Inilah tumpukan konteks ketika kita memasukkan subpanggilan pow(2, 2) :
Konteks: { x: 2, n: 2, pada baris 1 } pow(2, 2)
Konteks: { x: 2, n: 3, pada baris 5 } pow(2, 3)
Konteks eksekusi baru saat ini ada di atas (dan dicetak tebal), dan konteks yang diingat sebelumnya ada di bawah.
Saat kita menyelesaikan subpanggilan – mudah untuk melanjutkan konteks sebelumnya, karena ini mempertahankan kedua variabel dan tempat persis kode di mana ia berhenti.
Harap dicatat:
Di sini, di gambar kita menggunakan kata “line”, karena dalam contoh kita hanya ada satu subpanggilan dalam satu baris, namun umumnya satu baris kode dapat berisi beberapa subpanggilan, seperti pow(…) + pow(…) + somethingElse(…) .
Jadi akan lebih tepat untuk mengatakan bahwa eksekusi dilanjutkan “segera setelah subcall”.
Prosesnya berulang: subpanggilan baru dibuat pada baris 5 , sekarang dengan argumen x=2 , n=1 .
Konteks eksekusi baru dibuat, konteks eksekusi sebelumnya didorong ke atas tumpukan:
Konteks: { x: 2, n: 1, pada baris 1 } pow(2, 1)
Konteks: { x: 2, n: 2, pada baris 5 } pow(2, 2)
Konteks: { x: 2, n: 3, pada baris 5 } pow(2, 3)
Ada 2 konteks lama sekarang dan 1 sedang berjalan untuk pow(2, 1) .
Selama eksekusi pow(2, 1) , tidak seperti sebelumnya, kondisi n == 1 benar, jadi cabang pertama if berfungsi:
fungsi daya(x, n) {
jika (n == 1) {
kembalikan x;
} kalau tidak {
kembalikan x * kekuatan(x, n - 1);
}
} Tidak ada lagi panggilan bertumpuk, sehingga fungsinya selesai, mengembalikan 2 .
Saat fungsi selesai, konteks eksekusinya tidak diperlukan lagi, sehingga dihapus dari memori. Yang sebelumnya dikembalikan dari atas tumpukan:
Konteks: { x: 2, n: 2, pada baris 5 } pow(2, 2)
Konteks: { x: 2, n: 3, pada baris 5 } pow(2, 3)
Eksekusi pow(2, 2) dilanjutkan. Ia memiliki hasil subpanggilan pow(2, 1) , sehingga ia juga dapat menyelesaikan evaluasi x * pow(x, n - 1) , dengan mengembalikan 4 .
Kemudian konteks sebelumnya dikembalikan:
Konteks: { x: 2, n: 3, pada baris 5 } pow(2, 3)
Setelah selesai, kita mendapatkan hasil pow(2, 3) = 8 .
Kedalaman rekursi dalam kasus ini adalah: 3 .
Seperti yang dapat kita lihat dari ilustrasi di atas, kedalaman rekursi sama dengan jumlah maksimal konteks dalam tumpukan.
Perhatikan persyaratan memori. Konteks membutuhkan memori. Dalam kasus kami, menaikkan pangkat n sebenarnya memerlukan memori untuk n konteks, untuk semua nilai n yang lebih rendah.
Algoritme berbasis loop lebih menghemat memori:
fungsi daya(x, n) {
misalkan hasilnya = 1;
untuk (misalkan i = 0; i < n; i++) {
hasil *= x;
}
hasil pengembalian;
} pow berulang menggunakan konteks tunggal yang mengubah i dan result proses. Persyaratan memorinya kecil, tetap dan tidak bergantung pada n .
Rekursi apa pun dapat ditulis ulang sebagai satu lingkaran. Varian loop biasanya bisa dibuat lebih efektif.
…Tetapi terkadang penulisan ulang tidak sepele, terutama ketika suatu fungsi menggunakan subpanggilan rekursif yang berbeda bergantung pada kondisi dan menggabungkan hasilnya atau ketika percabangan lebih rumit. Dan pengoptimalannya mungkin tidak diperlukan dan sama sekali tidak sepadan dengan usaha yang dilakukan.
Rekursi dapat memberikan kode yang lebih pendek, lebih mudah dipahami dan didukung. Optimasi tidak diperlukan di setiap tempat, sebagian besar kita memerlukan kode yang baik, itulah mengapa digunakan.
Penerapan rekursi hebat lainnya adalah traversal rekursif.
Bayangkan, kita punya perusahaan. Struktur staf dapat direpresentasikan sebagai objek:
biarkan perusahaan = {
penjualan: [{
nama: 'John',
gaji: 1000
}, {
nama: 'Alice',
gaji: 1600
}],
perkembangan: {
situs: [{
nama: 'Petrus',
gaji: 2000
}, {
nama: 'Alex',
gaji: 1800
}],
internal: [{
nama: 'Jack',
gaji: 1300
}]
}
};Dengan kata lain, sebuah perusahaan memiliki departemen.
Sebuah departemen mungkin memiliki sejumlah staf. Misalnya, departemen sales memiliki 2 karyawan: John dan Alice.
Atau suatu departemen dapat dipecah menjadi subdepartemen, seperti development yang memiliki dua cabang: sites dan internals . Masing-masing dari mereka memiliki stafnya sendiri.
Mungkin juga ketika suatu subdepartemen berkembang, ia terbagi menjadi sub-subdepartemen (atau tim).
Misalnya, departemen sites di masa depan dapat dibagi menjadi beberapa tim untuk siteA dan siteB . Dan mereka, berpotensi, dapat terpecah lebih jauh lagi. Itu tidak ada dalam gambarannya, hanya sesuatu yang perlu diingat.
Sekarang katakanlah kita menginginkan suatu fungsi untuk mendapatkan jumlah seluruh gaji. Bagaimana kita bisa melakukan itu?
Pendekatan yang berulang-ulang tidaklah mudah, karena strukturnya tidak sederhana. Ide pertama mungkin adalah membuat company for over dengan subloop bersarang di departemen tingkat 1. Tapi kemudian kita memerlukan lebih banyak subloop bersarang untuk beralih ke staf di departemen tingkat 2 seperti sites … Dan kemudian subloop lain di dalam departemen tingkat 3 yang mungkin muncul di masa mendatang? Jika kita menempatkan 3-4 subloop bersarang dalam kode untuk melintasi satu objek, itu menjadi agak jelek.
Mari kita coba rekursi.
Seperti yang bisa kita lihat, saat fungsi kita menjumlahkan suatu departemen, ada dua kemungkinan kasus:
Entah itu departemen “sederhana” dengan banyak orang – maka kita dapat menjumlahkan gaji dalam satu putaran sederhana.
Atau objek dengan N subdepartemen – maka kita dapat melakukan N panggilan rekursif untuk mendapatkan jumlah masing-masing subdepartemen dan menggabungkan hasilnya.
Kasus pertama adalah dasar rekursi, kasus sepele, ketika kita mendapatkan sebuah array.
Kasus kedua ketika kita mendapatkan suatu objek adalah langkah rekursif. Tugas yang kompleks dibagi menjadi beberapa subtugas untuk departemen yang lebih kecil. Mereka mungkin akan terpecah lagi, tetapi cepat atau lambat perpecahan akan berakhir pada (1).
Algoritmenya mungkin lebih mudah dibaca dari kode:
let company = { // objek yang sama, dikompresi agar singkatnya
penjualan: [{nama: 'John', gaji: 1000}, {nama: 'Alice', gaji: 1600 }],
perkembangan: {
situs: [{nama: 'Peter', gaji: 2000}, {nama: 'Alex', gaji: 1800 }],
internal: [{nama: 'Jack', gaji: 1300}]
}
};
// Fungsi untuk melakukan pekerjaan
jumlah fungsiGaji(departemen) {
if (Array.isArray(departemen)) { // kasus (1)
return department.reduce((prev, current) => prev + current.salary, 0); // jumlahkan arraynya
} lain { // kasus (2)
misalkan jumlah = 0;
for (biarkan subdep dari Object.values(departemen)) {
jumlah += jumlahGaji(subdep); // memanggil subdepartemen secara rekursif, jumlahkan hasilnya
}
jumlah pengembalian;
}
}
alert(jumlahGaji(perusahaan)); // 7700Kodenya pendek dan mudah dimengerti (semoga?). Itulah kekuatan rekursi. Ini juga berfungsi untuk semua tingkat subdepartemen yang bersarang.
Berikut diagram panggilannya:
Kita dapat dengan mudah melihat prinsipnya: untuk suatu objek {...} subpanggilan dibuat, sedangkan array [...] adalah “daun” dari pohon rekursi, mereka memberikan hasil langsung.
Perhatikan bahwa kode ini menggunakan fitur pintar yang telah kita bahas sebelumnya:
Metode arr.reduce dijelaskan pada bab Metode array untuk mendapatkan jumlah array.
Ulangi for(val of Object.values(obj)) untuk mengulangi nilai objek: Object.values mengembalikan array dari nilai tersebut.
Struktur data rekursif (didefinisikan secara rekursif) adalah struktur yang mereplikasi dirinya sendiri dalam beberapa bagian.
Kita baru saja melihatnya pada contoh struktur perusahaan di atas.
Departemen perusahaan adalah:
Entah sekelompok orang.
Atau objek dengan departemen .
Untuk pengembang web ada contoh yang lebih terkenal: dokumen HTML dan XML.
Dalam dokumen HTML, tag HTML mungkin berisi daftar:
Potongan teks.
Komentar HTML.
Tag HTML lainnya (yang mungkin berisi potongan teks/komentar atau tag lain, dll).
Itu sekali lagi merupakan definisi rekursif.
Untuk pemahaman yang lebih baik, kita akan membahas satu lagi struktur rekursif bernama “Daftar tertaut” yang mungkin merupakan alternatif yang lebih baik untuk array dalam beberapa kasus.
Bayangkan, kita ingin menyimpan daftar objek yang diurutkan.
Pilihan alaminya adalah array:
biarkan arr = [obj1, obj2, obj3];
…Tapi ada masalah dengan array. Operasi “hapus elemen” dan “masukkan elemen” mahal. Misalnya, operasi arr.unshift(obj) harus memberi nomor ulang pada semua elemen untuk memberikan ruang bagi obj baru, dan jika arraynya besar, hal ini memerlukan waktu. Sama dengan arr.shift() .
Satu-satunya modifikasi struktural yang tidak memerlukan penomoran ulang secara massal adalah modifikasi yang beroperasi dengan akhir array: arr.push/pop . Jadi sebuah array bisa menjadi sangat lambat untuk antrian yang besar, ketika kita harus bekerja dari awal.
Alternatifnya, jika kita benar-benar membutuhkan penyisipan/penghapusan cepat, kita dapat memilih struktur data lain yang disebut daftar tertaut.
Elemen daftar tertaut didefinisikan secara rekursif sebagai objek dengan:
value .
properti next yang mereferensikan elemen daftar tertaut berikutnya atau null jika itu akhirnya.
Misalnya:
biarkan daftar = {
nilai: 1,
Berikutnya: {
nilai: 2,
Berikutnya: {
nilai: 3,
Berikutnya: {
nilai: 4,
selanjutnya: batal
}
}
}
};Representasi grafis dari daftar:
Kode alternatif untuk pembuatan:
misalkan daftar = { nilai: 1 };
daftar.berikutnya = { nilai: 2 };
daftar.next.next = { nilai: 3 };
daftar.next.next.next = { nilai: 4 };
daftar.next.next.next.next = null; Di sini kita dapat melihat dengan lebih jelas bahwa ada beberapa objek, masing-masing memiliki value dan next menunjuk ke tetangganya. Variabel list adalah objek pertama dalam rantai, jadi dengan mengikuti petunjuk next kita dapat menjangkau elemen apa pun.
Daftar ini dapat dengan mudah dibagi menjadi beberapa bagian dan kemudian digabungkan kembali:
biarkan SecondList = daftar.next.next; daftar.next.next = null;
Untuk bergabung:
daftar.next.next = Daftar kedua;
Dan tentunya kita bisa menyisipkan atau mengeluarkan item di mana saja.
Misalnya, untuk menambahkan nilai baru, kita perlu memperbarui bagian atas daftar:
misalkan daftar = { nilai: 1 };
daftar.berikutnya = { nilai: 2 };
daftar.next.next = { nilai: 3 };
daftar.next.next.next = { nilai: 4 };
// tambahkan nilai baru ke dalam daftar
daftar = { nilai: "item baru", selanjutnya: daftar }; Untuk menghapus nilai dari tengah, ubah nilai next dari nilai sebelumnya:
daftar.next = daftar.next.next;
Kami membuat list.next melompati 1 ke nilai 2 . Nilai 1 kini dikecualikan dari rantai. Jika tidak disimpan di tempat lain, maka secara otomatis akan terhapus dari memori.
Tidak seperti array, tidak ada penomoran ulang secara massal, kita dapat dengan mudah mengatur ulang elemen.
Tentu saja, daftar tidak selalu lebih baik daripada array. Kalau tidak, semua orang hanya akan menggunakan daftar.
Kelemahan utamanya adalah kita tidak dapat dengan mudah mengakses suatu elemen berdasarkan nomornya. Dalam array itu mudah: arr[n] adalah referensi langsung. Namun dalam daftar kita harus memulai dari item pertama dan melanjutkan next N kali untuk mendapatkan elemen ke-N.
…Tetapi kita tidak selalu membutuhkan operasi seperti itu. Misalnya, ketika kita membutuhkan antrian atau bahkan deque – struktur terurut yang harus memungkinkan penambahan/penghapusan elemen dengan sangat cepat dari kedua ujungnya, namun akses ke bagian tengahnya tidak diperlukan.
Daftar dapat ditingkatkan:
Kita dapat menambahkan properti prev selain next untuk mereferensikan elemen sebelumnya, untuk berpindah kembali dengan mudah.
Kita juga dapat menambahkan variabel bernama tail yang merujuk pada elemen terakhir daftar (dan memperbaruinya saat menambahkan/menghapus elemen dari akhir).
…Struktur data dapat bervariasi sesuai dengan kebutuhan kita.
Ketentuan:
Rekursi adalah istilah pemrograman yang berarti memanggil suatu fungsi dari dirinya sendiri. Fungsi rekursif dapat digunakan untuk menyelesaikan tugas dengan cara yang elegan.
Ketika suatu fungsi memanggil dirinya sendiri, itu disebut langkah rekursi . Dasar dari rekursi adalah argumen fungsi yang membuat tugas menjadi sangat sederhana sehingga fungsi tersebut tidak melakukan pemanggilan lebih lanjut.
Struktur data yang didefinisikan secara rekursif adalah struktur data yang dapat didefinisikan menggunakan struktur data itu sendiri.
Misalnya, daftar tertaut dapat didefinisikan sebagai struktur data yang terdiri dari objek yang mereferensikan daftar (atau nol).
daftar = { nilai, berikutnya -> daftar }Pohon seperti pohon elemen HTML atau pohon departemen dari bab ini juga bersifat rekursif: mereka memiliki cabang dan setiap cabang dapat memiliki cabang lainnya.
Fungsi rekursif dapat digunakan untuk menjalankannya seperti yang kita lihat pada contoh sumSalary .
Fungsi rekursif apa pun dapat ditulis ulang menjadi fungsi berulang. Dan itu terkadang diperlukan untuk mengoptimalkan berbagai hal. Namun untuk banyak tugas, solusi rekursif cukup cepat dan lebih mudah untuk ditulis dan didukung.
pentingnya: 5
Tulislah fungsi sumTo(n) yang menghitung jumlah bilangan 1 + 2 + ... + n .
Misalnya:
jumlahKe(1) = 1 jumlahTo(2) = 2 + 1 = 3 jumlahKe(3) = 3 + 2 + 1 = 6 jumlahKe(4) = 4 + 3 + 2 + 1 = 10 ... jumlahTo(100) = 100 + 99 + ... + 2 + 1 = 5050
Buatlah 3 varian solusi:
Menggunakan perulangan for.
Menggunakan rekursi, menyebabkan sumTo(n) = n + sumTo(n-1) untuk n > 1 .
Menggunakan rumus perkembangan aritmatika.
Contoh hasilnya:
function sumTo(n) { /*... kode Anda ... */ }
peringatan(jumlahTo(100) ); // 5050PS Varian solusi manakah yang tercepat? Paling lambat? Mengapa?
PPS Bisakah kita menggunakan rekursi untuk menghitung sumTo(100000) ?
Solusi menggunakan loop:
fungsi jumlahTo(n) {
misalkan jumlah = 0;
untuk (misalkan i = 1; i <= n; i++) {
jumlah += saya;
}
jumlah pengembalian;
}
peringatan(jumlahTo(100) );Solusi menggunakan rekursi:
fungsi jumlahTo(n) {
jika (n == 1) kembalikan 1;
kembalikan n + jumlahTo(n - 1);
}
peringatan(jumlahTo(100) ); Penyelesaiannya menggunakan rumus: sumTo(n) = n*(n+1)/2 :
fungsi jumlahTo(n) {
kembali n * (n + 1) / 2;
}
peringatan(jumlahTo(100) ); PS Tentu saja rumusnya adalah solusi tercepat. Ia hanya menggunakan 3 operasi untuk nomor apa pun n . Matematika membantu!
Varian loop adalah yang kedua dalam hal kecepatan. Baik dalam varian rekursif maupun loop, kami menjumlahkan angka yang sama. Namun rekursi melibatkan panggilan bersarang dan manajemen tumpukan eksekusi. Itu juga membutuhkan sumber daya, jadi lebih lambat.
PPS Beberapa mesin mendukung pengoptimalan “panggilan ekor”: jika panggilan rekursif adalah panggilan terakhir dalam fungsi tersebut, tanpa ada penghitungan lain yang dilakukan, maka fungsi luar tidak perlu melanjutkan eksekusi, sehingga mesin tidak perlu melakukannya ingat konteks eksekusinya. Itu menghilangkan beban memori. Namun jika mesin JavaScript tidak mendukung optimasi tail call (sebagian besar tidak mendukungnya), akan terjadi kesalahan: ukuran tumpukan maksimum terlampaui, karena biasanya ada batasan pada ukuran tumpukan total.
pentingnya: 4
Faktorial suatu bilangan asli adalah bilangan yang dikalikan dengan "number minus one" lalu dikalikan dengan "number minus two" dan seterusnya hingga 1 . Faktorial dari n dilambangkan dengan n!
Kita dapat menulis definisi faktorial seperti ini:
N! = n * (n - 1) * (n - 2) * ...*1
Nilai faktorial untuk n yang berbeda :
1! = 1 2! = 2 * 1 = 2 3! = 3*2*1 = 6 4! = 4*3*2*1 = 24 5! = 5*4*3*2*1 = 120
Tugasnya adalah menulis fungsi factorial(n) yang menghitung n! menggunakan panggilan rekursif.
waspada( faktorial(5) ); // 120
PS Petunjuk: n! dapat ditulis sebagai n * (n-1)! Misalnya: 3! = 3*2! = 3*2*1! = 6
Menurut definisi, faktorial n! dapat ditulis sebagai n * (n-1)! .
Dengan kata lain, hasil factorial(n) dapat dihitung sebagai n dikalikan dengan hasil factorial(n-1) . Dan panggilan untuk n-1 dapat turun secara rekursif semakin rendah, hingga 1 .
fungsi faktorial(n) {
kembali (n != 1) ? n * faktorial(n - 1) : 1;
}
waspada( faktorial(5) ); // 120 Dasar rekursi adalah nilai 1 . Kita juga dapat menjadikan 0 sebagai basis di sini, tidak terlalu menjadi masalah, namun memberikan satu langkah rekursif lagi:
fungsi faktorial(n) {
kembali n? n * faktorial(n - 1) : 1;
}
waspada( faktorial(5) ); // 120pentingnya: 5
Barisan bilangan Fibonacci mempunyai rumus F n = F n-1 + F n-2 . Dengan kata lain, bilangan berikutnya merupakan penjumlahan dari dua bilangan sebelumnya.
Dua bilangan pertama adalah 1 , lalu 2(1+1) , lalu 3(1+2) , 5(2+3) dan seterusnya: 1, 1, 2, 3, 5, 8, 13, 21... .
Angka Fibonacci berhubungan dengan rasio emas dan banyak fenomena alam di sekitar kita.
Tulis fungsi fib(n) yang mengembalikan bilangan Fibonacci n-th .
Contoh pekerjaan:
fungsi fib(n) { /* kode Anda */ }
peringatan(fib(3)); // 2
peringatan(fib(7)); // 13
peringatan(fib(77)); // 5527939700884757 PS Fungsinya harus cepat. Panggilan ke fib(77) seharusnya memakan waktu tidak lebih dari sepersekian detik.
Solusi pertama yang bisa kita coba di sini adalah solusi rekursif.
Angka Fibonacci bersifat rekursif menurut definisi:
fungsi fib(n) {
kembali n <= 1 ? n : fib(n - 1) + fib(n - 2);
}
peringatan( fib(3) ); // 2
peringatan( fib(7) ); // 13
// kebohongan(77); // akan sangat lambat! …Tetapi untuk nilai n yang besar itu sangat lambat. Misalnya, fib(77) mungkin mematikan mesin untuk beberapa waktu dan memakan semua sumber daya CPU.
Itu karena fungsinya membuat terlalu banyak subpanggilan. Nilai-nilai yang sama dievaluasi kembali berulang kali.
Misalnya, mari kita lihat perhitungan untuk fib(5) :
... fib(5) = fib(4) + fib(3) fib(4) = fib(3) + fib(2) ...
Di sini kita dapat melihat bahwa nilai fib(3) diperlukan untuk fib(5) dan fib(4) . Jadi fib(3) akan dipanggil dan dievaluasi dua kali secara independen.
Inilah pohon rekursi lengkap:
Kita dapat dengan jelas melihat bahwa fib(3) dievaluasi dua kali dan fib(2) dievaluasi tiga kali. Jumlah total komputasi tumbuh jauh lebih cepat daripada n , menjadikannya sangat besar bahkan untuk n=77 .
Kita dapat mengoptimalkannya dengan mengingat nilai yang telah dievaluasi: jika nilai katakanlah fib(3) dihitung satu kali, maka kita dapat menggunakannya kembali dalam penghitungan selanjutnya.
Varian lainnya adalah menghentikan rekursi dan menggunakan algoritma berbasis loop yang sama sekali berbeda.
Daripada berpindah dari n ke nilai yang lebih rendah, kita bisa membuat perulangan yang dimulai dari 1 dan 2 , lalu mendapatkan fib(3) sebagai jumlah keduanya, lalu fib(4) sebagai jumlah dari dua nilai sebelumnya, lalu fib(5) dan naik dan naik, hingga mencapai nilai yang dibutuhkan. Pada setiap langkah kita hanya perlu mengingat dua nilai sebelumnya.
Berikut adalah langkah-langkah algoritma baru secara detail.
Awal:
// a = fib(1), b = fib(2), nilai-nilai ini menurut definisi 1 misalkan a = 1, b = 1; // dapatkan c = fib(3) sebagai jumlah mereka misalkan c = a + b; /* kita sekarang mempunyai fib(1), fib(2), fib(3) a b c 1, 1, 2 */
Sekarang kita ingin mendapatkan fib(4) = fib(2) + fib(3) .
Mari kita geser variabelnya: a,b akan mendapatkan fib(2),fib(3) , dan c akan mendapatkan jumlahnya:
a = b; // sekarang a = fib(2) b = c; // sekarang b = fib(3) c = a + b; // c = fib(4) /* sekarang kita mempunyai urutannya: a b c 1, 1, 2, 3 */
Langkah selanjutnya memberikan nomor urut lain:
a = b; // sekarang a = fib(3)
b = c; // sekarang b = fib(4)
c = a + b; // c = fib(5)
/* sekarang urutannya adalah (satu angka lagi):
a b c
1, 1, 2, 3, 5
*/…Dan seterusnya sampai kita mendapatkan nilai yang dibutuhkan. Itu jauh lebih cepat daripada rekursi dan tidak melibatkan penghitungan duplikat.
Kode lengkapnya:
fungsi fib(n) {
misalkan a = 1;
misalkan b = 1;
untuk (misalkan i = 3; i <= n; i++) {
misalkan c = a + b;
a = b;
b = c;
}
kembali b;
}
peringatan( fib(3) ); // 2
peringatan( fib(7) ); // 13
waspada( fib(77) ); // 5527939700884757 Perulangan dimulai dengan i=3 , karena nilai urutan pertama dan kedua dikodekan ke dalam variabel a=1 , b=1 .
Pendekatan ini disebut pemrograman dinamis bottom-up.
pentingnya: 5
Katakanlah kita memiliki daftar tertaut tunggal (seperti yang dijelaskan dalam bab Rekursi dan tumpukan):
biarkan daftar = {
nilai: 1,
Berikutnya: {
nilai: 2,
Berikutnya: {
nilai: 3,
Berikutnya: {
nilai: 4,
selanjutnya: batal
}
}
}
}; Tulis fungsi printList(list) yang menampilkan item daftar satu per satu.
Buatlah dua varian solusi: menggunakan loop dan menggunakan rekursi.
Mana yang lebih baik: dengan atau tanpa rekursi?
Varian solusi berbasis loop:
biarkan daftar = {
nilai: 1,
Berikutnya: {
nilai: 2,
Berikutnya: {
nilai: 3,
Berikutnya: {
nilai: 4,
selanjutnya: batal
}
}
}
};
fungsi printList(daftar) {
biarkan tmp = daftar;
sementara (tmp) {
peringatan(tmp.nilai);
tmp = tmp.berikutnya;
}
}
printList(daftar); Harap dicatat bahwa kami menggunakan variabel sementara tmp untuk menelusuri daftar. Secara teknis, kita bisa menggunakan list parameter fungsi sebagai gantinya:
fungsi printList(daftar) {
sementara(daftar) {
alert(daftar.nilai);
daftar = daftar.berikutnya;
}
} …Tapi itu tidak bijaksana. Di masa depan kita mungkin perlu memperluas suatu fungsi, melakukan hal lain dengan daftarnya. Jika kita mengubah list , maka kita kehilangan kemampuan tersebut.
Berbicara tentang nama variabel yang bagus, list di sini adalah daftarnya sendiri. Elemen pertama darinya. Dan seharusnya tetap seperti itu. Itu jelas dan dapat diandalkan.
Dari sisi lain, peran tmp secara eksklusif adalah penjelajahan daftar, seperti i dalam perulangan for .
Varian rekursif dari printList(list) mengikuti logika sederhana: untuk menampilkan daftar, kita harus menampilkan elemen saat ini list , lalu lakukan hal yang sama untuk list.next :
biarkan daftar = {
nilai: 1,
Berikutnya: {
nilai: 2,
Berikutnya: {
nilai: 3,
Berikutnya: {
nilai: 4,
selanjutnya: batal
}
}
}
};
fungsi printList(daftar) {
alert(daftar.nilai); // menampilkan item saat ini
if (daftar.berikutnya) {
printList(daftar.berikutnya); // lakukan hal yang sama untuk sisa daftar
}
}
printList(daftar);Sekarang apa yang lebih baik?
Secara teknis, loop ini lebih efektif. Kedua varian ini melakukan hal yang sama, namun loop tidak menghabiskan sumber daya untuk pemanggilan fungsi bertingkat.
Di sisi lain, varian rekursif lebih pendek dan terkadang lebih mudah dipahami.
pentingnya: 5
Keluarkan daftar tertaut tunggal dari tugas sebelumnya Keluarkan daftar tertaut tunggal dalam urutan terbalik.
Buatlah dua solusi: menggunakan loop dan menggunakan rekursi.
Logika rekursif agak rumit di sini.
Pertama-tama kita perlu menampilkan sisa daftarnya dan kemudian menampilkan yang sekarang:
biarkan daftar = {
nilai: 1,
Berikutnya: {
nilai: 2,
Berikutnya: {
nilai: 3,
Berikutnya: {
nilai: 4,
selanjutnya: batal
}
}
}
};
fungsi printReverseList(daftar) {
if (daftar.berikutnya) {
printReverseList(daftar.berikutnya);
}
alert(daftar.nilai);
}
printReverseList(daftar);
Varian loop juga sedikit lebih rumit daripada keluaran langsung.
Tidak ada cara untuk mendapatkan nilai terakhir dalam list kami. Kita juga tidak bisa “kembali”.
Jadi yang bisa kita lakukan adalah pertama-tama menelusuri item-item dalam urutan langsung dan mengingatnya dalam sebuah array, lalu menampilkan apa yang kita ingat dalam urutan terbalik:
biarkan daftar = {
nilai: 1,
Berikutnya: {
nilai: 2,
Berikutnya: {
nilai: 3,
Berikutnya: {
nilai: 4,
selanjutnya: batal
}
}
}
};
fungsi printReverseList(daftar) {
biarkan arr = [];
biarkan tmp = daftar;
sementara (tmp) {
arr.push(tmp.nilai);
tmp = tmp.berikutnya;
}
for (misalkan i = arr.length - 1; i >= 0; i--) {
waspada( arr[i] );
}
}
printReverseList(daftar);Harap dicatat bahwa solusi rekursif sebenarnya melakukan hal yang persis sama: ia mengikuti daftar, mengingat item dalam rantai panggilan bersarang (dalam tumpukan konteks eksekusi), dan kemudian mengeluarkannya.