1.
Setelah membaca bagian ini dan menjalankan sel-sel kode SageMath, tulislah beberapa kalimat yang menjelaskan pengamatan Anda tentang manfaat solusi eksplisit bagi persamaan rekurensi dibandingkan dengan menghitung nilai-nilainya secara rekursif.
Subbab 9.8 Diskusi
Yolanda menyeruput kopinya. “Aku senang sudah memperhatikan ketika kita mempelajari ruang vektor, basis, dan dimensi. Semua pembahasan tentang solusi persamaan rekurensi ini benar-benar masuk akal. Aku juga sungguh memahami mengapa profesor begitu menekankan pemfaktoran. Kita sudah melihatnya pada semester pertama ketika mempelajari pecahan parsial dalam kalkulus. Lalu kita melihatnya lagi dalam pembahasan persamaan diferensial. Bukankah sangat menarik melihat bagaimana semuanya saling berkaitan?” Semangat sebesar itu terlalu berlebihan bagi Alice, yang sedang mengalami hari yang buruk. Bob lebih bersimpati dan berkata, “Kecuali perincian tentang nol sebagai akar polinom operator pemajuan, aku tidak bermasalah dengan bab ini.” Xing berkata, “Di sini kita mempelajari pendekatan saksama yang hanya bergantung pada pemfaktoran. Aku sudah membaca-baca di web dan melihat bahwa belum lama ini ada beberapa terobosan dalam pemfaktoran.” Bob segera menimpali, “Namun, sekalipun kamu sangat mahir memfaktorkan, jika persamaan operator pemajuanmu memuat polinom berderajat besar, syarat awalnya akan banyak. Ini mungkin menjadi kendala besar kedua.” Dave bergumam, “Faktorkan saja. Selebihnya mudah.” Carlos kembali diam, tetapi ia tahu Dave benar. Menyelesaikan sistem persamaan linear yang besar relatif mudah. Tantangannya terletak pada tahap pemfaktoran.
Walaupun menganggap materi bab ini menarik, Bob juga bertanya-tanya apakah mereka benar-benar memerlukan semua perangkat tersebut. “Mendefinisikan fungsi rekursif itu mudah dalam hampir semua bahasa pemrograman, jadi mengapa tidak menggunakan komputer saja untuk menghitung nilai yang diperlukan?” Xing mulai berkomentar bahwa teknik-teknik dalam bab ini dapat memberikan cara yang baik untuk memahami laju pertumbuhan fungsi rekursif melalui notasi O besar dari Bab 4, tetapi Alice menyela dengan mengusulkan suatu eksperimen pemrograman yang dapat memperbaiki suasana hatinya. (Kesempatan untuk membuktikan Bob keliru mungkin lebih memotivasinya daripada kesempatan menulis kode, tetapi ia tidak ingin bersikap terlalu kejam.)
1
Sejarah masuknya rekursi ke dalam ALGOL (dan dengan demikian ke dalam kebanyakan bahasa pemrograman modern) melibatkan sejumlah intrik. Maarten van Emden menceritakannya dalam tulisan blog berjudul “How recursion got into programming: a tale of intrigue, betrayal, and advanced programming-language semantics”.
Kelompok itu memutuskan untuk meninjau rekurensi dalam Contoh 9.25, yang segera mereka tuliskan sebagai fungsi rekursif pada bilangan bulat tak negatif:
\begin{equation*}
r(n) =\begin{cases} 2^n + r(n-1) + 2r(n-2)\amp \text{jika }n\geq 2;\\
1\amp\text{jika }n=1;\\
2\amp\text{jika }n=0.\end{cases}
\end{equation*}
Alice mengambil komputernya, mengimplementasikan fungsi tersebut dalam SageMath, lalu menghitung beberapa nilai uji.
Kemudian ia mendefinisikan fungsi kedua,
s, yaitu solusi eksplisit (nonrekursif) dari Contoh 9.25, lalu memeriksa bahwa nilai-nilainya sama.
“Eksperimen ini mau dibawa ke mana?” tanya Bob dengan tidak sabar. Untuk nilai-nilai tersebut, baik
r maupun s tampaknya memberikan jawaban sama cepatnya. Dave berkata bahwa ia pernah mendengar perintah timeit dalam SageMath yang memungkinkan mereka membandingkan waktu eksekusi, lalu mengambil alih papan ketik Alice untuk mengetik:
Hasil ini akhirnya menarik perhatian Bob karena waktu eksekusi
s tampak relatif konstan meskipun \(n\) bertambah, sedangkan waktu eksekusi r tampaknya menjadi kira-kira 10 kali lebih lama setiap kali nilai \(n\) bertambah 5. Sebagai pengujian terakhir, mereka menjalankan kode SageMath di bawah ini, yang menghitung s(100) hampir seketika. Di sisi lain, tampaknya mengisi ulang kopi merupakan cara yang baik untuk melewatkan waktu sambil menunggu r(40).
