it-swarm-id.com

Dalam bahasa Inggris yang sederhana, apa itu rekursi?

Gagasan rekursi tidak terlalu umum di dunia nyata. Jadi, sepertinya agak membingungkan bagi para programmer pemula. Padahal, saya kira, mereka menjadi terbiasa dengan konsep itu secara bertahap. Jadi, apa yang bisa menjadi penjelasan yang bagus bagi mereka untuk memahami ide itu dengan mudah?

76
Gulshan

Untuk menjelaskan rekursi , saya menggunakan kombinasi penjelasan yang berbeda, biasanya untuk keduanya mencoba untuk:

  • jelaskan konsepnya,
  • jelaskan mengapa itu penting,
  • jelaskan bagaimana cara mendapatkannya.

Sebagai permulaan, Wolfram | Alpha mendefinisikannya dalam istilah yang lebih sederhana daripada Wikipedia :

Ekspresi sedemikian rupa sehingga setiap istilah dihasilkan dengan mengulangi operasi matematika tertentu.


Matematika

Jika siswa Anda (atau orang yang Anda jelaskan juga, mulai sekarang saya akan mengatakan siswa) memiliki setidaknya beberapa latar belakang matematika, mereka jelas sudah mengalami rekursi dengan mempelajari seri dan gagasan mereka tentang recursivity dan relasinya berulang .

Cara yang sangat baik untuk memulai adalah dengan menunjukkan dengan seri dan mengatakan bahwa ini adalah tentang rekursi:

  • fungsi matematika ...
  • ... yang memanggil dirinya sendiri untuk menghitung nilai yang sesuai dengan elemen ke-n ...
  • ... dan yang mendefinisikan beberapa batasan.

Biasanya, Anda mendapatkan "huh huh, whatev '" yang terbaik karena mereka masih tidak menggunakannya, atau lebih mungkin hanya mendengkur yang sangat dalam.


Contoh Pengodean

Untuk selebihnya, sebenarnya ini adalah versi terperinci dari apa yang saya sajikan dalam Addendum of jawaban saya untuk pertanyaan yang Anda tunjuk tentang pointer (kata-kata buruk).

Pada tahap ini, siswa saya biasanya tahu cara mencetak sesuatu ke layar. Dengan asumsi kita menggunakan C, mereka tahu cara mencetak char tunggal menggunakan write atau printf. Mereka juga tahu tentang loop kontrol.

Saya biasanya menggunakan beberapa masalah pemrograman yang berulang dan sederhana sampai mereka mendapatkannya:

Faktorial

Factorial adalah konsep matematika yang sangat sederhana untuk dipahami, dan implementasinya sangat dekat dengan representasi matematisnya. Namun, mereka mungkin tidak mendapatkannya pada awalnya.

Recursive Definition of the Factorial Operation

Abjad

Versi alfabet menarik untuk mengajar mereka memikirkan urutan pernyataan rekursif mereka. Seperti dengan pointer, mereka hanya akan melemparkan garis secara acak pada Anda. Intinya adalah untuk membawa mereka ke realisasi bahwa loop dapat dibalik dengan memodifikasi kondisi ATAU dengan hanya membalikkan urutan pernyataan dalam fungsi Anda. Di situlah pencetakan alfabet membantu, karena itu sesuatu yang visual bagi mereka. Cukup minta mereka menulis fungsi yang akan mencetak satu karakter untuk setiap panggilan, dan menyebut dirinya secara rekursif untuk menulis yang berikutnya (atau sebelumnya).

Penggemar FP, lewati fakta bahwa mencetak barang-barang ke arus keluaran adalah efek samping untuk saat ini ... Jangan terlalu menyebalkan pada FP-front. (Tetapi jika Anda menggunakan bahasa dengan dukungan daftar, jangan ragu untuk menggabungkan ke daftar di setiap iterasi dan hanya mencetak hasil akhir. Tapi biasanya saya mulai dengan C, yang sayangnya bukan yang terbaik untuk masalah dan konsep semacam ini) .

Eksponen

Masalah eksponensial sedikit lebih sulit ( pada tahap ini belajar). Jelas konsepnya persis sama dengan faktorial dan tidak ada kompleksitas tambahan ... kecuali Anda memiliki banyak parameter. Dan itu biasanya cukup untuk membingungkan orang dan membuang mereka di awal.

Bentuknya sederhana:

Simple Form of the Exponentiation Operation

dapat diekspresikan seperti ini dengan pengulangan:

Recurrence Relation for the Exponentiation Operation

Sulit

Setelah masalah-masalah sederhana ini telah ditunjukkan DAN diimplementasikan kembali dalam tutorial, Anda dapat memberikan latihan yang sedikit lebih sulit (tapi sangat klasik):

Catatan: Sekali lagi, beberapa di antaranya sebenarnya tidak lebih sulit ... Mereka hanya mendekati masalah dari sudut yang sama persis, atau yang sedikit berbeda. Tetapi latihan membuatnya sempurna.


Pembantu

Referensi

Beberapa bacaan tidak pernah sakit. Yah itu pada awalnya, dan mereka akan merasa lebih tersesat. Ini adalah jenis hal yang tumbuh pada Anda dan yang ada di belakang kepala Anda sampai suatu hari Anda menyadari bahwa Anda akhirnya mendapatkannya. Dan kemudian Anda memikirkan kembali hal-hal yang Anda baca ini. The rekursi , rekursi dalam Ilmu Komputer dan relasi pengulangan halaman di Wikipedia akan lakukan untuk sekarang.

Level/Kedalaman

Dengan asumsi siswa Anda tidak memiliki banyak pengalaman pengkodean, sediakan kode bertopik. Setelah upaya pertama, berikan mereka fungsi pencetakan yang dapat menampilkan tingkat rekursi. Mencetak nilai numerik level membantu.

Diagram Stack-as-Drawers

Indentasi hasil cetak (atau output level) juga membantu, karena memberikan representasi visual lain tentang apa yang sedang dilakukan program Anda, membuka dan menutup konteks tumpukan seperti laci, atau folder di Explorer sistem file.

Akronim Rekursif

Jika siswa Anda sudah sedikit berpengalaman dalam budaya komputer, mereka mungkin sudah menggunakan beberapa proyek/perangkat lunak dengan nama menggunakan akronim rekursif . Sudah menjadi tradisi untuk beberapa waktu, terutama dalam proyek GNU. Beberapa contoh termasuk:

Rekursif:

  • GNU - "GNU's Not Unix"
  • Nagios - "Nagios Tidak Akan Bersikeras Kesucian"
  • PHP - "PHP Hypertext Preprocessor" (dan originall "Personal Home Page")
  • Wine - "Anggur Bukan Emulator"
  • Zile - "Zile Is Lossy Emacs"

Saling Rekursif:

  • HURD - "HIRD of Unix-Replacing Daemon" (di mana HIRD adalah "HURD Antarmuka yang mewakili Kedalaman")

Mintalah mereka mencoba untuk membuat sendiri.

Demikian pula, ada banyak kejadian humor rekursif, seperti Pencarian rekursif Google koreksi. Untuk informasi lebih lanjut tentang rekursi, baca jawaban ini .


Perangkap dan Pembelajaran Lebih Lanjut

Beberapa masalah yang biasanya dihadapi orang dan untuk itu Anda perlu tahu jawabannya.

Kenapa, oh Tuhan Kenapa ???

Kenapa kamu ingin melakukan itu? Alasan yang baik tetapi tidak jelas adalah bahwa seringkali lebih mudah untuk mengungkapkan masalah dengan cara itu. Alasan yang tidak begitu bagus tapi jelas adalah bahwa sering kali mengetik kurang (jangan membuat mereka merasa begitu buruk hanya menggunakan rekursi ...).

Beberapa masalah pasti lebih mudah dipecahkan ketika menggunakan pendekatan rekursif. Biasanya, masalah apa pun yang dapat Anda pecahkan menggunakan paradigma Divide and Conquer akan sesuai dengan algoritma rekursi multi-cabang.

Apa N lagi ??

Mengapa n saya atau (apa pun nama variabel Anda) berbeda setiap kali? Pemula biasanya memiliki masalah dalam memahami variabel dan parameter apa, dan bagaimana hal-hal yang bernama n dalam program Anda dapat memiliki nilai yang berbeda. Jadi sekarang jika nilai ini ada di loop kontrol atau rekursi, itu bahkan lebih buruk! Bersikaplah Baik dan jangan menggunakan nama variabel yang sama di mana-mana, dan jelaskan bahwa parameter hanyalah variabel.

Kondisi Akhir

Bagaimana cara menentukan kondisi akhir saya? Itu mudah, minta mereka mengatakan langkah-langkahnya dengan keras. Misalnya untuk faktorial mulai dari 5, lalu 4, lalu ... hingga 0.

Iblis ada di Rincian

Jangan berbicara dengan hal-hal awal tentang hal seperti optimisasi panggilan ekor . Saya tahu, saya tahu, TCO bagus, tetapi pada awalnya mereka tidak peduli. Beri mereka waktu untuk membungkus kepala mereka di sekitar proses dengan cara yang bekerja untuk mereka. Jangan ragu untuk menghancurkan dunia mereka lagi nanti, tetapi beri mereka istirahat.

Demikian pula, jangan berbicara langsung dari kuliah pertama tentang call stack dan konsumsi memorinya dan ... well ... the stack overflow . Saya sering mengajari siswa secara pribadi yang menunjukkan kepada saya ceramah di mana mereka memiliki 50 slide tentang semuanya ada yang tahu tentang rekursi ketika mereka hampir tidak bisa menulis loop dengan benar pada tahap ini. Itu contoh yang bagus tentang bagaimana referensi akan membantu nanti tetapi sekarang hanya membingungkan Anda sangat.

Tapi tolong, pada waktunya, jelaskan bahwa ada alasan untuk beralih berulang atau rekursif .

Rekursi Saling

Kami telah melihat bahwa fungsi dapat bersifat rekursif, dan bahkan mereka dapat memiliki beberapa titik panggilan (8-queens, Hanoi, Fibonacci atau bahkan algoritma eksplorasi untuk kapal penyapu ranjau). Tapi bagaimana dengan panggilan rekursif yang saling ? Mulai dengan matematika di sini juga. f(x) = g(x) + h(x) di mana g(x) = f(x) + l(x) dan h dan l lakukan saja.

Dimulai dengan hanya seri matematika membuatnya lebih mudah untuk menulis dan mengimplementasikan karena kontrak didefinisikan dengan jelas oleh ekspresi. Misalnya, Urutan Hofstadter Wanita dan Pria :

Hofstadter's Male and Female Sequences

Namun dalam hal kode, perlu dicatat bahwa implementasi dari solusi yang saling rekursif sering mengarah pada duplikasi kode dan lebih baik disederhanakan menjadi bentuk rekursif tunggal (Lihat Peter Norvig 's Memecahkan Teka-teki Sudoku Setiap .

111
haylem

Pemanggilan fungsi dari dalam fungsi yang sama.

59
ChaosPandion

Rekursi adalah fungsi yang memanggil dirinya sendiri.

Cara menggunakannya, kapan menggunakannya dan bagaimana menghindari desain yang buruk penting untuk diketahui, yang mengharuskan Anda untuk mencobanya sendiri, dan memahami apa yang terjadi.

Hal terpenting yang perlu Anda ketahui adalah berhati-hati untuk tidak mendapatkan perulangan yang tidak pernah berakhir. Jawaban dari pramodc84 untuk pertanyaan Anda memiliki kesalahan ini: Tidak pernah berakhir ...
Fungsi rekursif harus selalu memeriksa kondisi untuk menentukan apakah harus memanggil dirinya lagi atau tidak.

Contoh paling klasik untuk menggunakan rekursi, adalah bekerja dengan pohon tanpa kedalaman statis. Ini adalah tugas yang harus Anda gunakan rekursi.

27
awe

Pemrograman rekursif adalah proses mengurangi masalah secara progresif untuk lebih mudah menyelesaikan versi-versi itu sendiri.

Setiap fungsi rekursif cenderung untuk:

  1. ambil daftar untuk diproses, atau beberapa struktur lain, atau domain masalah
  2. berurusan dengan titik/langkah saat ini
  3. menyebut dirinya sendiri dengan sisanya/subdomain
  4. menggabungkan atau menggunakan hasil kerja subdomain

Ketika langkah 2 adalah sebelum 3, dan ketika langkah 4 sepele (gabungan, jumlah, atau tidak sama sekali) ini memungkinkan rekursi ekor . Langkah 2 seringkali harus datang setelah langkah 3, karena hasil dari subdomain dari masalah mungkin diperlukan untuk menyelesaikan langkah saat ini.

Ambil lintasan pohon biner lurus ke depan. Traversal dapat dibuat dalam pre-order, in-order, atau post-order, tergantung pada apa yang diperlukan.

   B
A     C

Pemesanan sebelumnya: B A C

traverse(tree):
    visit the node
    traverse(left)
    traverse(right)

Pemesanan: A B C

traverse(tree):
    traverse(left)
    visit the node
    traverse(right)

Post-order: A C B

traverse(tree):
    traverse(left)
    traverse(right)
    visit the node

Sangat banyak masalah rekursif yang merupakan kasus spesifik dari operasi peta , atau lipat - pemahaman hanya dua operasi ini dapat mengarah pada pemahaman yang signifikan tentang kasus penggunaan yang baik untuk rekursi.

21
Orbling

OP mengatakan bahwa rekursi tidak ada di dunia nyata, tetapi saya mohon berbeda.

Mari kita ambil 'operasi' dunia nyata memotong pizza. Anda telah mengeluarkan pizza dari oven dan untuk menyajikannya, Anda harus memotongnya menjadi dua, kemudian memotong setengahnya menjadi dua, kemudian memotong lagi setengahnya menjadi dua.

Operasi memotong pizza yang Anda lakukan berulang-ulang sampai Anda mendapatkan hasil yang Anda inginkan (jumlah irisan). Demi argumen, katakanlah pizza yang tidak dipotong adalah irisan itu sendiri.

Berikut ini contoh di Ruby:

 def cut_pizza (existing_slices, diinginkan_slices) 
 jika existing_slices! = diinginkan_slices 
 # kami belum memiliki cukup irisan untuk memberi makan semua orang, jadi 
 # kami memotong irisan pizza, sehingga menggandakan nomor mereka 
 new_slices = existing_slices * 2 
 # dan ini adalah panggilan rekursif 
 cut_pizza (new_slices, diinginkan_slices) 
 lain 
 # kami memiliki jumlah irisan yang diinginkan, jadi kami kembali 
 # di sini alih-alih terus berulang 
 mengembalikan irisan yang ada 
 akhir 
 akhir 
 
 pizza = 1 # seluruh pizza, 'one slice' 
 cut_pizza (pizza, 8) # => kita akan mendapatkan 8 

Jadi operasi dunia nyata adalah memotong pizza, dan rekursi melakukan hal yang sama berulang-ulang sampai Anda mendapatkan apa yang Anda inginkan.

Operasi Anda akan menemukan bahwa memotong yang dapat Anda terapkan dengan fungsi rekursif adalah:

  • Menghitung bunga majemuk selama beberapa bulan.
  • Mencari file di sistem file (karena sistem file adalah pohon karena direktori).
  • Apa pun yang melibatkan bekerja dengan pohon secara umum, kurasa.

Saya sarankan menulis program untuk mencari file berdasarkan nama file itu, dan mencoba untuk menulis fungsi yang memanggil dirinya sendiri sampai ditemukan, tanda tangannya akan terlihat seperti ini:

find_file_by_name(file_name_we_are_looking_for, path_to_look_in)

Jadi Anda bisa menyebutnya seperti ini:

find_file_by_name('httpd.conf', '/etc') # damn it i can never find Apache's conf

Ini hanya pemrograman mekanika menurut pendapat saya, cara cerdas menghapus duplikasi. Anda dapat menulis ulang ini dengan menggunakan variabel, tetapi ini adalah solusi 'lebih baik'. Tidak ada yang misterius atau sulit tentang hal itu. Anda akan menulis beberapa fungsi rekursif, itu akan mengklik dan huzzah trik mekanis lain di kotak alat pemrograman Anda.

Kredit Ekstra Contoh cut_pizza Di atas akan memberi Anda tingkat kesalahan yang terlalu dalam jika Anda meminta sejumlah irisan yang bukan kekuatan 2 (yaitu 2 atau 4 atau 8 atau 16). Bisakah Anda memodifikasinya sehingga jika seseorang meminta 10 irisan, ia tidak akan berjalan selamanya?

20
Ryan Allen

Oke saya akan mencoba untuk menjaga ini tetap sederhana dan ringkas.

Fungsi rekursif adalah fungsi yang menyebut dirinya. Fungsi rekursif terdiri dari tiga hal:

  1. Logika
  2. Panggilan untuk dirinya sendiri
  3. Kapan harus mengakhiri.

Cara terbaik untuk menulis metode rekursif, adalah dengan memikirkan metode yang Anda coba tulis sebagai contoh sederhana hanya menangani satu loop dari proses yang ingin Anda ulangi, kemudian tambahkan panggilan ke metode itu sendiri, dan tambahkan ketika Anda ingin mengakhiri. Cara terbaik untuk belajar adalah berlatih seperti semua hal lainnya.

Karena ini adalah situs web programmer, saya akan menahan diri untuk tidak menulis kode, tetapi ini bagus tautan

jika Anda mendapat lelucon itu, Anda mendapatkan makna rekursi.

16
dustyprogrammer

Rekursi adalah alat yang dapat digunakan oleh programmer untuk menjalankan panggilan fungsi. Urutan Fibonacci adalah contoh buku teks tentang bagaimana rekursi digunakan.

Kebanyakan kode rekursif jika tidak semua dapat dinyatakan sebagai fungsi berulang, tetapi biasanya berantakan. Contoh bagus dari program rekursif lainnya adalah Struktur Data seperti pohon, pohon pencarian biner dan bahkan quicksort.

Rekursi digunakan untuk membuat kode kurang ceroboh, perlu diingat biasanya lebih lambat dan membutuhkan lebih banyak memori.

6
Bryan Harrington

Saya suka menggunakan ini:

Bagaimana Anda berjalan ke toko?

Jika Anda berada di pintu masuk toko, cukup lewati saja. Jika tidak, ambil satu langkah, lalu berjalan ke toko.

Sangat penting untuk memasukkan tiga aspek:

  • Kasus dasar sepele
  • Memecahkan sebagian kecil dari masalah
  • Memecahkan sisa masalah secara rekursif

Kami banyak menggunakan rekursi dalam kehidupan sehari-hari; kami hanya tidak berpikir seperti itu.

5
Barry Brown

Contoh terbaik yang saya tunjukkan kepada Anda adalah Bahasa Pemrograman C oleh K & R. Dalam buku itu (dan saya mengutip dari ingatan), entri dalam halaman indeks untuk rekursi (sendiri) mencantumkan halaman aktual tempat mereka berbicara tentang rekursi dan halaman indeks juga.

3
Kanini

Josh K sudah menyebutkan boneka Matroshka . Anggaplah Anda ingin mempelajari sesuatu yang hanya diketahui oleh boneka terpendek. Masalahnya adalah bahwa Anda tidak dapat benar-benar berbicara dengannya secara langsung, karena dia awalnya hidup di dalam boneka yang lebih tinggi yang pada gambar pertama ditempatkan di sebelah kirinya. Struktur ini berjalan seperti itu (boneka hidup di dalam boneka yang lebih tinggi) sampai berakhir hanya dengan yang tertinggi.

Jadi, satu-satunya hal yang dapat Anda lakukan adalah mengajukan pertanyaan kepada boneka tertinggi. Boneka tertinggi (yang tidak tahu jawabannya) perlu meneruskan pertanyaan Anda ke boneka pendek (yang pada gambar pertama ada di sebelah kanannya). Karena dia juga tidak punya jawaban, dia perlu bertanya boneka pendek berikutnya. Ini akan berjalan seperti itu sampai pesan mencapai boneka terpendek. Boneka terpendek (yang merupakan satu-satunya yang tahu jawaban rahasia) akan meneruskan jawaban ke boneka yang lebih tinggi berikutnya (ditemukan di sebelah kirinya), yang akan meneruskannya ke boneka yang lebih tinggi berikutnya ... dan ini akan berlanjut sampai jawabannya mencapai tujuan akhirnya, yang merupakan boneka tertinggi dan akhirnya ... kamu :)

Inilah yang sebenarnya dilakukan rekursi. Fungsi/metode memanggil dirinya sendiri hingga mendapatkan jawaban yang diharapkan. Itu sebabnya ketika Anda menulis kode rekursif, sangat penting untuk memutuskan kapan rekursi akan berakhir.

Bukan penjelasan terbaik tetapi semoga membantu.

2
sakisk

Rekursi n. - Suatu pola desain algoritma di mana suatu operasi didefinisikan sesuai dengan sendirinya.

Contoh klasiknya adalah menemukan faktorial suatu angka, n !. 0! = 1, dan untuk bilangan asli N lainnya, faktorial N adalah produk dari semua bilangan asli kurang dari atau sama dengan N. Jadi, 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720. Definisi dasar ini akan memungkinkan Anda untuk membuat solusi berulang sederhana:

int Fact(int degree)
{
    int result = 1;
    for(int i=degree; i>1; i--)
       result *= i;

    return result;
}

Namun, periksa kembali operasinya. 6! = 6 * 5 * 4 * 3 * 2 * 1. Dengan definisi yang sama, 5! = 5 * 4 * 3 * 2 * 1, artinya kita dapat mengatakan 6! = 6 * (5!). Pada gilirannya, 5! = 5 * (4!) Dan seterusnya. Dengan melakukan ini, kami mengurangi masalah ke operasi yang dilakukan pada hasil semua operasi sebelumnya. Ini pada akhirnya mereduksi menjadi titik, yang disebut kasus dasar, di mana hasilnya diketahui menurut definisi. Dalam kasus kami, 0! = 1 (dalam kebanyakan kasus kami juga bisa mengatakan bahwa 1! = 1). Dalam komputasi, kita sering diizinkan mendefinisikan algoritme dengan cara yang sangat mirip, dengan memanggil metode itu sendiri dan mengirimkan input yang lebih kecil, sehingga mengurangi masalah melalui banyak rekursi ke kasing dasar:

int Fact(int degree)
{
    if(degree==0) return 1; //the base case; 0! = 1 by definition
    else return degree * Fact(degree -1); //the recursive case; N! = N*(N-1)!
}

Ini dapat, dalam banyak bahasa, selanjutnya disederhanakan menggunakan operator ternary (kadang-kadang dilihat sebagai fungsi Iif dalam bahasa yang tidak menyediakan operator seperti itu):

int Fact(int degree)
{
    //reads equivalently to the above, but is concise and often optimizable
    return degree==0 ? 1: degree * Fact(degree -1);
}

Keuntungan:

  • Ekspresi alami - untuk banyak jenis algoritma, ini adalah cara yang sangat alami untuk mengekspresikan fungsi.
  • Reduced LOC - Seringkali jauh lebih ringkas untuk mendefinisikan suatu fungsi secara rekursif.
  • Kecepatan - Dalam kasus tertentu, tergantung pada bahasa dan arsitektur komputer, rekursi suatu algoritma lebih cepat daripada solusi iteratif yang setara, biasanya karena membuat panggilan fungsi adalah operasi yang lebih cepat pada tingkat perangkat keras daripada operasi dan akses memori yang diperlukan untuk mengulang secara berulang.
  • Divisibilitas - Banyak algoritma rekursif adalah dari mentalitas "divide and conquer"; hasil operasi adalah fungsi dari hasil operasi yang sama yang dilakukan pada masing-masing dua bagian dari input. Ini memungkinkan Anda untuk membagi pekerjaan menjadi dua di setiap level, dan jika tersedia Anda dapat memberikan setengahnya lagi kepada "unit eksekusi" untuk diproses. Ini biasanya lebih sulit atau tidak mungkin dengan algoritma iteratif.

Kekurangan:

  • Membutuhkan pemahaman - Anda hanya harus "memahami" konsep rekursi untuk memahami apa yang terjadi, dan karenanya menulis dan memelihara algoritma rekursif yang efektif. Kalau tidak, itu hanya terlihat seperti ilmu hitam.
  • Tergantung pada konteks - Apakah rekursi adalah ide yang baik atau tidak tergantung pada seberapa elegan algoritme dapat didefinisikan berdasarkan dirinya sendiri. Meskipun dimungkinkan untuk membangun, misalnya, SelectionSort rekursif, algoritma iteratif biasanya lebih dimengerti.
  • Perdagangan RAM akses untuk tumpukan panggilan - Biasanya, panggilan fungsi lebih murah daripada akses cache, yang dapat membuat rekursi lebih cepat daripada iterasi. Tapi, biasanya ada batas kedalaman tumpukan panggilan yang dapat menyebabkan rekursi ke kesalahan di mana algoritma iteratif akan bekerja.
  • Rekursi tak terbatas - Anda harus tahu kapan harus berhenti. Iterasi tak terbatas juga dimungkinkan tetapi konstruk perulangan yang terlibat biasanya lebih mudah dipahami dan dengan demikian untuk debug.
2
KeithS

Contoh yang saya gunakan adalah masalah yang saya hadapi dalam kehidupan nyata. Anda memiliki wadah (seperti tas ransel besar yang ingin Anda bawa bepergian) dan Anda ingin mengetahui berat totalnya. Anda memiliki dua atau tiga benda lepas dalam wadah, dan beberapa wadah lainnya (misalnya, barang karung.) Berat total kontainer jelas adalah berat wadah kosong ditambah berat segala sesuatu di dalamnya. Untuk barang-barang yang longgar, Anda bisa menimbangnya, dan untuk barang-barang karung Anda bisa menimbangnya atau Anda bisa mengatakan "well, berat masing-masing kantong barang adalah berat wadah kosong plus berat segala sesuatu di dalamnya". Dan kemudian Anda terus masuk ke dalam wadah ke dalam wadah dan seterusnya sampai Anda sampai pada titik di mana hanya ada item longgar di dalam wadah. Itu rekursi.

Anda mungkin berpikir itu tidak pernah terjadi dalam kehidupan nyata, tetapi bayangkan mencoba menghitung, atau menambah gaji, orang-orang di perusahaan atau divisi tertentu, yang memiliki campuran orang-orang yang hanya bekerja untuk perusahaan, orang-orang di divisi, kemudian di divisi ada departemen dan sebagainya. Atau penjualan di negara yang memiliki wilayah, beberapa di antaranya memiliki subregional, dll. Masalah seperti ini selalu terjadi dalam bisnis.

1
Kate Gregory

Rekursi dapat digunakan untuk memecahkan banyak masalah penghitungan. Misalnya, Anda memiliki sekelompok n orang di sebuah pesta (n> 1), dan semua orang menjabat tangan orang lain satu kali. Berapa banyak jabat tangan terjadi? Anda mungkin tahu bahwa solusinya adalah C (n, 2) = n (n-1)/2, tetapi Anda dapat menyelesaikannya secara rekursif sebagai berikut:

Misalkan hanya ada dua orang. Maka (dengan inspeksi) jawabannya jelas 1.

Misalkan Anda memiliki tiga orang. Pilih satu orang, dan perhatikan bahwa dia berjabat tangan dengan dua orang lainnya. Setelah itu Anda harus menghitung hanya jabat tangan antara dua orang lainnya. Kami sudah melakukan itu sekarang, dan itu adalah 1. Jadi jawabannya adalah 2 + 1 = 3.

Misalkan Anda memiliki n orang. Mengikuti logika yang sama seperti sebelumnya, itu adalah (n-1) + (jumlah jabat tangan antara n-1 orang). Memperluas, kita mendapatkan (n-1) + (n-2) + ... + 1.

Dinyatakan sebagai fungsi rekursif,

f (2) = 1
f (n) = n-1 + f (n-1), n> 2

0
Mitch Schwartz

Berikut adalah contoh nyata untuk rekursi.

Biarkan mereka membayangkan bahwa mereka memiliki koleksi komik dan Anda akan mencampur semuanya menjadi tumpukan besar. Hati-hati - jika mereka benar-benar memiliki koleksi, mereka dapat langsung membunuh Anda ketika Anda hanya menyebutkan ide untuk melakukannya.

Sekarang biarkan mereka mengurutkan tumpukan komik yang tidak disortir ini dengan bantuan manual ini:

Manual: How to sort a pile of comics

Check the pile if it is already sorted. If it is, then done.

As long as there are comics in the pile, put each one on another pile, 
ordered from left to right in ascending order:

    If your current pile contains different comics, pile them by comic.
    If not and your current pile contains different years, pile them by year.
    If not and your current pile contains different tenth digits, pile them 
    by this digit: Issue 1 to 9, 10 to 19, and so on.
    If not then "pile" them by issue number.

Refer to the "Manual: How to sort a pile of comics" to separately sort each
of the new piles.

Collect the piles back to a big pile from left to right.

Done.

Yang menyenangkan di sini adalah: Ketika mereka pergi ke satu masalah, mereka memiliki "tumpukan bingkai" penuh dengan tumpukan lokal terlihat sebelum mereka di tanah. Berikan mereka beberapa cetakan manual dan sisihkan satu tingkat setiap tumpukan dengan tanda di mana Anda saat ini pada tingkat ini (yaitu keadaan variabel lokal), sehingga Anda dapat melanjutkan di sana pada setiap Selesai.

Itulah yang pada dasarnya tentang rekursi: Melakukan proses yang sama, hanya pada level detail yang lebih halus, semakin Anda masuk ke dalamnya.

0
Secure

Dalam kehidupan (tidak seperti dalam program komputer) rekursi jarang terjadi di bawah kendali langsung kita, karena dapat membingungkan untuk mewujudkannya. Juga, persepsi cenderung tentang efek samping, daripada fungsional murni, jadi jika rekursi terjadi, Anda mungkin tidak menyadarinya.

Rekursi memang terjadi di sini di dunia. Banyak.

Contoh yang baik adalah (versi sederhana) siklus air:

  • Matahari memanaskan danau
  • Air naik ke langit dan membentuk awan
  • Awan melayang ke gunung
  • Di gunung udara menjadi terlalu dingin untuk mempertahankan kelembabannya
  • Hujan turun
  • Bentuk sungai
  • Air di sungai mengalir ke danau

Ini adalah siklus yang menyebabkan dirinya terjadi lagi. Itu rekursif.

Tempat lain yang bisa Anda dapatkan adalah rekursi dalam bahasa Inggris (dan bahasa manusia pada umumnya). Anda mungkin tidak mengenalinya pada awalnya, tetapi cara kita dapat menghasilkan kalimat bersifat rekursif, karena aturan memungkinkan kita untuk menyematkan satu contoh simbol di samping instance lain dari simbol yang sama.

Dari Steven Pinker's The Language Instinct:

jika gadis itu makan es krim atau gadis itu makan permen maka anak itu makan hot dog

Itu adalah seluruh kalimat yang berisi seluruh kalimat lain:

gadis itu makan es krim

gadis itu makan permen

bocah itu makan hot dog

Tindakan memahami kalimat lengkap melibatkan memahami kalimat yang lebih kecil, yang menggunakan perangkat tipuan mental yang sama untuk dipahami sebagai kalimat lengkap.

Untuk memahami rekursi dari perspektif pemrograman, paling mudah untuk melihat masalah yang dapat diselesaikan dengan rekursi, dan memahami mengapa itu harus terjadi dan apa artinya itu yang harus Anda lakukan.

Sebagai contoh, saya akan menggunakan fungsi pembagi umum terbesar, atau singkatnya gcd.

Anda memiliki dua angka Anda a dan b. Untuk menemukan gcd mereka (dengan asumsi tidak ada 0), Anda perlu memeriksa apakah a dapat dibagi secara merata menjadi b. Jika ya b adalah gcd, jika tidak, Anda perlu memeriksa gcd dari b dan sisanya dari a/b.

Anda seharusnya sudah dapat melihat bahwa ini adalah fungsi rekursif, karena Anda memiliki fungsi gcd yang memanggil fungsi gcd. Hanya untuk memalu rumah, ini dia dalam c # (sekali lagi, anggap 0 tidak pernah dilewatkan sebagai parameter):

int gcd(int a, int b)
{   
    if (a % b == 0) //this is a stopping condition
    {
        return b;
    }

    return (gcd(b, a % b)); //the call to gcd here makes this function recursive
}

Dalam sebuah program, penting untuk memiliki kondisi berhenti, jika tidak, fungsi Anda akan berulang selamanya, yang pada akhirnya akan menyebabkan stack overflow!

Alasan untuk menggunakan rekursi di sini, daripada loop sementara atau konstruk berulang lainnya, adalah bahwa ketika Anda membaca kode itu memberitahu Anda apa yang dilakukannya dan apa yang akan terjadi selanjutnya, sehingga lebih mudah untuk mencari tahu apakah itu bekerja dengan benar .

0
Matt Ellen