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 terbiasa dengan konsep itu secara bertahap. Jadi, apa yang bisa menjadi penjelasan yang bagus bagi mereka untuk memahami gagasan itu dengan mudah?

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

• 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 sudah jelas mengalami rekursi dengan mempelajari seri dan gagasan tentang rekursif dan hubungan perulangan mereka .

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

• fungsi matematika ...
• ... yang memanggil dirinya 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 di Addendum dari jawaban saya untuk pertanyaan yang Anda tunjuk tentang pointer ( permainan kata-kata buruk).

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

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

• yang faktorial operasi,
• printer alfabet,
• printer alfabet terbalik,
• yang exponentation operasi.

Faktorial

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

Huruf

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 hanya dengan membalik 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 ke aliran output adalah efek samping untuk saat ini ... Jangan terlalu mengganggu front-FP. (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) .}

Eksponensial

Masalah eksponensial sedikit lebih sulit ( pada tahap pembelajaran ini). Jelas konsepnya persis sama dengan faktorial dan tidak ada kerumitan tambahan ... kecuali Anda memiliki banyak parameter. Dan itu biasanya cukup untuk membingungkan orang dan mengusir mereka pada awalnya.

Bentuknya sederhana:

dapat diekspresikan seperti ini dengan pengulangan:

Lebih keras

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

• The Fibonacci angka,
• The Greatest Divisor umum ,
• Masalah 8-Queens ,
• Game The Towers of Hanoi ,
• Dan jika Anda memiliki lingkungan grafis (atau dapat memberikan potongan kode untuk itu atau untuk keluaran terminal atau mereka sudah dapat mengaturnya), hal-hal seperti:
  • Fraktal Serpihan Salju Koch ,
  • Segitiga Sierpinski .
• Dan untuk contoh praktis, pertimbangkan menulis:
  • algoritma traversal pohon,
  • parser ekspresi matematika sederhana,
  • permainan kapal penyapu ranjau.

Catatan: Sekali lagi, beberapa di antaranya sebenarnya tidak lebih sulit ... Mereka hanya mendekati masalah dari sudut yang persis sama, atau yang sedikit berbeda. Tetapi latihan menjadi 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 hubungan pengulangan halaman di Wikipedia akan lakukan untuk saat ini.

Tingkat / 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

Mengindentasi 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 dalam penjelajah 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-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 koreksi pencarian rekursif Google . 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 terlalu bagus tapi jelas adalah bahwa sering kali mengetik kurang (jangan membuat mereka merasa begitu buruk hanya menggunakan rekursi ...).

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

Apa N lagi ??

Mengapa saya natau (apa pun nama variabel Anda) berbeda setiap kali? Pemula biasanya memiliki masalah dalam memahami variabel dan parameter apa, dan bagaimana hal-hal yang disebutkan ndalam 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-hal seperti optimasi panggilan ekor . Saya tahu, saya tahu, TCO itu baik, 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 bicara langsung dari kuliah pertama tentang panggilan stack dan konsumsi memorinya dan ... well ... stack overflow . Saya sering mengajari siswa secara pribadi yang menunjukkan kepada saya ceramah di mana mereka memiliki 50 slide tentang semua yang perlu diketahui tentang rekursi ketika mereka hampir tidak dapat menulis satu lingkaran dengan benar pada tahap ini. Itu adalah contoh yang baik tentang bagaimana referensi akan membantu nanti tetapi saat ini hanya membuat Anda bingung .

Tapi tolong, pada waktunya, jelaskan bahwa ada alasan untuk menempuh rute 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 yang saling rekursif ? Mulai dengan matematika di sini juga. f(x) = g(x) + h(x)di mana g(x) = f(x) + l(x)dan hdan lhanya melakukan hal-hal.

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

Namun dalam hal kode, perlu dicatat bahwa implementasi solusi rekursif yang saling menguntungkan sering mengarah pada duplikasi kode dan lebih baik disederhanakan menjadi bentuk rekursif tunggal (Lihat Peter Norvig 's Solving Every Sudoku Puzzle .

Pemanggilan fungsi dari dalam fungsi yang sama.

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 sendiri lagi atau tidak.

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

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 sering 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

Pre-order: BAC

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

In-order: ABC

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

Post-order: ACB

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

Sangat banyak masalah rekursif adalah kasus-kasus khusus dari operasi peta , atau lipatan - pemahaman hanya dua operasi ini dapat menyebabkan pemahaman yang signifikan tentang kasus penggunaan yang baik untuk rekursi.

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 setengah.

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 ada_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 di sini 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
    kembalikan yang sudah ada
  akhir
akhir

pizza = 1 # pizza utuh, 'satu potong'
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 pada umumnya, 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 mekanik 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.

Ekstra Kredit The cut_pizzacontoh di atas akan memberikan tingkat tumpukan kesalahan terlalu dalam jika Anda meminta untuk sejumlah irisan yang bukan merupakan kekuatan 2 (yaitu 2 atau 4 atau 8 atau 16). Bisakah Anda memodifikasinya sehingga jika seseorang meminta 10 irisan, ia tidak akan berjalan selamanya?

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 tidak akan menulis kode, tetapi di sini ada tautan yang bagus

jika Anda mendapat lelucon itu, Anda mendapatkan makna rekursi.

Rekursi adalah alat yang bisa 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.

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 masalah
• Memecahkan sisa masalah secara rekursif

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

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.

Josh K sudah menyebutkan boneka Matroshka . Anggaplah Anda ingin mempelajari sesuatu yang hanya diketahui oleh boneka terpendek. Masalahnya adalah Anda tidak dapat berbicara dengannya secara langsung, karena dia awalnya tinggal di dalam boneka yang lebih tinggi yang pada gambar pertama diletakkan 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.

Rekursi n. - Pola desain algoritmik di mana 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 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 operasinya lagi. 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 akhirnya mereduksi menjadi titik, yang disebut kasus dasar, di mana hasilnya dikenal dengan definisi. Dalam kasus kami, 0! = 1 (dalam kebanyakan kasus, kami juga dapat 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 berulang 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 separuh lainnya ke "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 sedang terjadi, dan karenanya menulis dan memelihara algoritma rekursif yang efektif. Kalau tidak, itu hanya terlihat seperti ilmu hitam.
• Context-dependen - Apakah rekursi adalah ide yang bagus atau tidak tergantung pada seberapa elegan algoritme dapat didefinisikan sesuai dengan sendirinya. Meskipun dimungkinkan untuk membangun, misalnya, SelectionSort rekursif, algoritma iteratif biasanya lebih dimengerti.
• Memperdagangkan akses RAM 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 kesalahan rekursi 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.

Contoh yang saya gunakan adalah masalah yang saya hadapi dalam kehidupan nyata. Anda memiliki sebuah wadah (seperti ransel besar yang ingin Anda bawa bepergian) dan Anda ingin mengetahui berat totalnya. Anda memiliki di dalam wadah dua atau tiga benda lepas, dan beberapa wadah lainnya (katakanlah, barang-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.

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

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 peroleh adalah 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 lainnya:

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 serangkaian 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 nomor adan b. Untuk menemukan gcd mereka (dengan asumsi tidak ada 0), Anda perlu memeriksa apakah adapat dibagi secara merata b. Jika itu adalah bgcd, jika tidak, Anda perlu memeriksa gcd bdan sisanya 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 memberi tahu Anda apa yang dilakukannya dan apa yang akan terjadi selanjutnya, sehingga lebih mudah untuk mengetahui apakah itu bekerja dengan benar .

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 sampai pada satu masalah, mereka memiliki "tumpukan bingkai" penuh dengan tumpukan lokal terlihat sebelum mereka di tanah. Beri 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 dasarnya tentang rekursi: Melakukan proses yang sama, hanya pada level detail yang lebih halus, semakin Anda masuk ke dalamnya.

• Hentikan jika kondisi keluar tercapai
• melakukan sesuatu untuk mengubah keadaan
• lakukan semua pekerjaan mulai dengan keadaan saat ini

Rekursi adalah cara yang sangat ringkas untuk mengekspresikan sesuatu yang harus diulangi sampai sesuatu tercapai.

Bukan bahasa Inggris polos, bukan contoh kehidupan nyata, tetapi dua cara belajar rekursi dengan bermain:

• Menara Hanoi
• Baguenaudier

Penjelasan yang bagus tentang rekursi secara harfiah adalah 'tindakan yang terulang kembali dari dalam dirinya sendiri ".

Pertimbangkan seorang pelukis mengecat dinding, itu bersifat rekursif karena tindakannya adalah "mengecat strip dari langit-langit ke lantai daripada bergeser sedikit ke kanan dan (cat strip dari langit-langit ke lantai daripada bergeser sedikit ke kanan dan (cat a strip dari langit-langit ke lantai daripada bergeser sedikit ke kanan dan (dll))) ".

Fungsi paint () memanggil dirinya berulang kali untuk membuat fungsi paint_wall () yang lebih besar.

Semoga pelukis malang ini memiliki semacam kondisi berhenti :)