Sumber daya untuk meningkatkan pemahaman Anda tentang rekursi? [Tutup]

Saya tahu apa itu rekursi (ketika patten terulang kembali dalam dirinya sendiri, biasanya fungsi yang menyebut dirinya pada salah satu garisnya, setelah kondisional breakout ... kan?), Dan saya bisa memahami fungsi rekursif jika saya mempelajarinya dengan cermat. Masalah saya adalah, ketika saya melihat contoh-contoh baru, saya awalnya selalu bingung. Jika saya melihat lingkaran, atau pemetaan, zip, bersarang, panggilan polimorfik, dan sebagainya, saya tahu apa yang terjadi hanya dengan melihatnya. Ketika saya melihat kode rekursif, proses pemikiran saya biasanya 'apakah ini?' diikuti oleh 'oh itu rekursif' diikuti oleh 'Saya kira itu harus berhasil, jika mereka mengatakan itu berhasil.'

Jadi, apakah Anda punya tips / rencana / sumber daya untuk membangun keterampilan di bidang ini? Rekursi adalah semacam konsep aneh jadi saya berpikir cara untuk mengatasinya mungkin sama aneh dan tidak jelas.

Mulailah dengan sesuatu yang sederhana dan lacak dengan pensil dan kertas. Seriosuly. Tempat yang baik untuk memulai adalah algoritma pohon-traversal, karena mereka jauh lebih mudah ditangani menggunakan rekursi daripada iterasi biasa. Itu tidak harus menjadi contoh yang rumit, tetapi sesuatu yang sederhana dan Anda dapat bekerja dengannya.

Ya, ini aneh dan terkadang kontra-intuitif, tetapi begitu berbunyi klik, begitu Anda mengatakan "Eureka!" Anda akan bertanya-tanya bagaimana Anda tidak memahaminya sebelumnya! ;) Saya menyarankan pohon karena mereka (IMO) struktur paling mudah untuk dipahami dalam rekursi, dan mereka mudah digunakan dengan menggunakan pensil dan kertas. ;)

Saya sangat merekomendasikan Skema, menggunakan buku The Little Lisper. Setelah selesai, Anda akan memahami rekursi, jauh di lubuk hati. Hampir dijamin.

Saya pasti menyarankan SICP. Juga, Anda harus melihat video kursus pengantar penulis di sini ; mereka sangat membuka pikiran.

Jalan lain, yang tidak terlalu terkait dengan pemrograman, adalah membaca Gödel, Escher, Bach: Eternal Golden Braid oleh Hofstadter. Setelah Anda melaluinya, rekursi akan terlihat sealami aritmatika. Juga, Anda akan diyakinkan bahwa P = nP dan Anda akan ingin membangun mesin berpikir - tetapi itu adalah efek samping yang sangat kecil jika dibandingkan dengan manfaatnya.

Pada dasarnya itu hanya datang ke praktek ... Ambil masalah umum (menyortir, mencari, masalah matematika, dll) dan lihat apakah Anda dapat melihat cara di mana masalah tersebut dapat diselesaikan jika Anda menerapkan fungsi tunggal beberapa kali.

Misalnya pengurutan cepat beroperasi di mana ia memindahkan elemen dalam daftar menjadi dua bagian dan kemudian berlaku sendiri untuk masing-masing bagian tersebut. Ketika penyortiran awal terjadi itu tidak khawatir tentang mendapatkan dua bagian diurutkan pada saat itu. Melainkan mengambil elemen pivot dan menempatkan semua elemen lebih kecil dari elemen itu di satu sisi dan semua elemen lebih besar dari atau sama dengan di sisi lain. Apakah ini masuk akal bagaimana secara rekursif dapat memanggil dirinya sendiri pada saat itu untuk mengurutkan dua daftar yang lebih kecil? Mereka juga daftar. Hanya lebih kecil. Tapi mereka masih perlu disortir.

Kekuatan di balik rekursi adalah gagasan memecah belah dan menaklukkan. Pecahkan masalah berulang kali menjadi masalah yang lebih kecil yang sifatnya identik tetapi hanya lebih kecil. Jika Anda melakukannya cukup pada akhirnya Anda sampai pada titik di mana satu-satunya bagian yang tersisa sudah terpecahkan maka Anda hanya bekerja jalan keluar dari loop dan masalahnya selesai. Pelajarilah contoh-contoh yang Anda sebutkan sampai Anda memahaminya . Mungkin butuh beberapa saat tetapi akhirnya akan lebih mudah. Kemudian cobalah untuk mengambil masalah lain dan membuat fungsi rekursif untuk menyelesaikannya! Semoga berhasil!

EDIT: Saya juga harus menambahkan bahwa elemen kunci untuk rekursi adalah kemampuan dijamin dari fungsi untuk dapat berhenti. Ini berarti pemecahan masalah asli harus terus-menerus menjadi lebih kecil dan akhirnya harus ada titik berhenti yang dijamin (titik di mana sub masalah baru dapat dipecahkan atau sudah diselesaikan).

Secara pribadi saya pikir taruhan terbaik Anda adalah melalui latihan.

Saya belajar rekursi dengan LOGO. Anda bisa menggunakan LISP. Rekursi alami dalam bahasa-bahasa itu. Kalau tidak, Anda bisa menyamakannya dengan studi suite dan seri matematika di mana Anda mengekspresikan apa yang selanjutnya berdasarkan apa yang datang sebelumnya, yaitu u (n + 1) = f (u (n)), atau seri yang lebih kompleks di mana Anda memiliki banyak variabel dan beberapa dependensi, mis. u (n) = g (u (n-1), u (n-2), v (n), v (n-1)); v (n) = h (u (n-1), u (n-2), v (n), v (n-1)) ...

Jadi saran saya adalah agar Anda menemukan "masalah" rekursi standar yang sederhana (dalam ekspresi mereka) dan mencoba dan menerapkannya dalam bahasa pilihan Anda. Berlatih akan membantu Anda mempelajari cara berpikir, membaca, dan mengekspresikan "masalah" itu. Perhatikan bahwa seringkali beberapa dari masalah ini dapat diekspresikan melalui iterasi, tetapi rekursi mungkin merupakan cara yang lebih elegan untuk menyelesaikannya. Salah satunya adalah perhitungan angka faktorial.

"Masalah" grafis yang saya temukan membuatnya lebih mudah dilihat. Jadi lihatlah serpihan Koch, Fibonacci, kurva naga dan fraktal secara umum. Tetapi lihat juga algoritma quick-sort ...

Anda perlu membuat crash beberapa program (loop tanpa akhir, penggunaan sementara sumber daya tak terbatas), dan salah penanganan kondisi akhir (untuk mendapatkan hasil yang tidak terduga) sebelum Anda menyelesaikan semua itu. Dan bahkan ketika Anda mendapatkannya, Anda masih akan membuat kesalahan itu, hanya lebih jarang.

Struktur dan Interpretasi Program Komputer

Hal ini yang buku yang digunakan untuk belajar, bukan hanya rekursi, tetapi pemrograman secara umum di berbagai universitas. Ini adalah salah satu buku dasar yang menghasilkan lebih banyak informasi, semakin banyak pengalaman yang Anda dapatkan dan semakin banyak Anda membacanya.

Seperti halnya saya suka SICP dan Gödel, Escher, Bach: Eternal Golden Braid , Tourisky's LISP: A Softly Introduction to Symbolic Computation juga melakukan pekerjaan yang baik dalam memperkenalkan rekursi.

Konsep dasarnya adalah ini: Pertama, Anda harus tahu kapan fungsi rekursif Anda selesai, sehingga dapat mengembalikan hasilnya. Kemudian, Anda harus tahu cara mengambil kasus yang belum selesai, dan menguranginya menjadi sesuatu yang dapat Anda kembalikan. Untuk contoh faktorial (N) tradisional, Anda selesai ketika N <= 1, dan kasus yang belum selesai adalah N * faktorial (N-1).

Sebagai contoh yang jauh lebih jelek, ada fungsi Ackermann A (m, n).

A(0,n) = n+1.                                   This is the terminal case.
A(m,0) = A(m-1,1) if m > 0.                     This is a simple recursion.
A(m,n) = A(m-1, A(m, n-1)) if m > 0 and n > 0.  This one is ugly.

Saya sarankan bermain-main dengan beberapa bahasa fungsional gaya-ML seperti OCaml atau Haskell. Saya menemukan bahwa sintaksis pencocokan pola benar- benar membantu saya memahami bahkan fungsi rekursif yang relatif rumit, tentu jauh lebih baik daripada Skema ifdan condpernyataan. (Saya belajar Haskell dan Skema pada saat yang sama.)

Berikut contoh sepele untuk kontras:

(define (fib n)
   (cond [(= n 0) 0]
         [(= n 1) 1]
         [else (+ (fib (- n 1)) (fib (- n 2)))]))

dan dengan pencocokan pola:

fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

Contoh ini tidak benar-benar melakukan keadilan perbedaan - saya tidak pernah punya masalah dengan versi fungsi yang mana pun. Hanya untuk menggambarkan seperti apa kedua pilihan itu. Setelah Anda mendapatkan fungsi yang jauh lebih kompleks, menggunakan hal-hal seperti daftar dan pohon, perbedaannya menjadi lebih jelas.

Saya sangat merekomendasikan Haskell karena ini adalah bahasa yang sederhana dengan sintaks yang sangat bagus. Ini juga membuat lebih mudah untuk bekerja dengan ide-ide yang lebih maju seperti koreksi :

fibs = 0 : 1 : zipWith (+) fibs (drop 1 fibs)
fib n = fibs !! n

(Anda tidak akan mengerti kode di atas sampai Anda bermain sedikit dengan Haskell, tetapi yakinlah bahwa itu pada dasarnya ajaib: P.) Tentu saja Anda dapat melakukan hal yang sama dengan stream dalam Skema, tetapi jauh lebih alami di Haskell.

Itu tidak dicetak, tetapi jika Anda dapat menemukannya, "Algoritma Rekursif" oleh Richard Lorentz adalah tentang apa-apa selain rekursi. Ini mencakup dasar-dasar rekursi, serta algoritma rekursif tertentu.

Contoh-contohnya ada dalam Pascal, tetapi tidak begitu besar sehingga pilihan bahasa menyusahkan.