Apa itu rekursi dan kapan saya harus menggunakannya?

Salah satu topik yang tampaknya muncul secara teratur di milis dan diskusi online adalah manfaat (atau kekurangannya) melakukan gelar Ilmu Komputer. Sebuah argumen yang tampaknya muncul berkali-kali untuk pihak negatif adalah bahwa mereka telah melakukan pengkodean selama beberapa tahun dan mereka tidak pernah menggunakan rekursi.

Jadi pertanyaannya adalah:

1. Apa itu rekursi?
2. Kapan saya akan menggunakan rekursi?
3. Mengapa orang tidak menggunakan rekursi?

Ada sejumlah penjelasan bagus tentang rekursi di utas ini, jawaban ini adalah tentang mengapa Anda tidak boleh menggunakannya di sebagian besar bahasa. * Di sebagian besar implementasi bahasa imperatif utama (yaitu setiap implementasi utama C, C ++, Basic, Python , Ruby, Java, dan C #) iterasi adalah jauh lebih baik untuk rekursi.

Untuk mengetahui alasannya, ikuti langkah-langkah yang digunakan bahasa di atas untuk memanggil suatu fungsi:

1. spasi diukir di tumpukan untuk argumen fungsi dan variabel lokal
2. argumen fungsi disalin ke ruang baru ini
3. kontrol melompat ke fungsi
4. kode fungsi berjalan
5. hasil fungsi disalin menjadi nilai kembali
6. tumpukan digulung kembali ke posisi sebelumnya
7. kontrol melompat kembali ke tempat fungsi itu dipanggil

Melakukan semua langkah ini membutuhkan waktu, biasanya sedikit lebih lama daripada yang diperlukan untuk mengulang melalui satu putaran. Namun, masalah sebenarnya ada di langkah # 1. Ketika banyak program mulai, mereka mengalokasikan satu potongan memori untuk tumpukan mereka, dan ketika mereka kehabisan memori itu (seringkali, tetapi tidak selalu karena rekursi), program macet karena tumpukan melimpah .

Jadi dalam bahasa-bahasa ini rekursi lebih lambat dan membuat Anda rentan mengalami error. Masih ada beberapa argumen untuk menggunakannya. Secara umum, kode yang ditulis secara rekursif lebih pendek dan sedikit lebih elegan, setelah Anda tahu cara membacanya.

Ada teknik yang dapat digunakan oleh pelaksana bahasa yang disebut pengoptimalan panggilan ekor yang dapat menghilangkan beberapa kelas stack overflow. Singkatnya: jika ekspresi kembalian fungsi hanyalah hasil dari pemanggilan fungsi, maka Anda tidak perlu menambahkan level baru ke tumpukan, Anda dapat menggunakan kembali level saat ini untuk fungsi yang dipanggil. Sayangnya, beberapa implementasi bahasa imperatif memiliki pengoptimalan tail-call bawaan.

* Saya suka rekursi. Bahasa statis favorit saya tidak menggunakan loop sama sekali, rekursi adalah satu-satunya cara untuk melakukan sesuatu berulang kali. Saya hanya tidak berpikir bahwa rekursi umumnya merupakan ide bagus dalam bahasa yang tidak disetel untuk itu.

** Ngomong-ngomong Mario, nama tipikal untuk fungsi ArrangeString Anda adalah "join", dan saya akan terkejut jika bahasa pilihan Anda belum menerapkannya.

Contoh bahasa Inggris sederhana dari rekursi.

A child couldn't sleep, so her mother told her a story about a little frog,
    who couldn't sleep, so the frog's mother told her a story about a little bear,
         who couldn't sleep, so the bear's mother told her a story about a little weasel... 
            who fell asleep.
         ...and the little bear fell asleep;
    ...and the little frog fell asleep;
...and the child fell asleep.

Dalam pengertian ilmu komputer yang paling dasar, rekursi adalah fungsi yang memanggil dirinya sendiri. Katakanlah Anda memiliki struktur daftar tertaut:

struct Node {
    Node* next;
};

Dan Anda ingin mengetahui berapa lama daftar tertaut Anda dapat melakukan ini dengan rekursi:

int length(const Node* list) {
    if (!list->next) {
        return 1;
    } else {
        return 1 + length(list->next);
    }
}

(Ini tentu saja bisa dilakukan dengan for loop juga, tetapi berguna sebagai ilustrasi konsep)

Setiap kali suatu fungsi memanggil dirinya sendiri, membuat loop, maka itu adalah rekursi. Seperti apapun, ada kegunaan baik dan kegunaan buruk untuk rekursi.

Contoh paling sederhana adalah rekursi ekor di mana baris terakhir fungsinya adalah panggilan ke dirinya sendiri:

int FloorByTen(int num)
{
    if (num % 10 == 0)
        return num;
    else
        return FloorByTen(num-1);
}

Namun, ini adalah contoh yang timpang, hampir tidak ada gunanya karena dapat dengan mudah diganti dengan iterasi yang lebih efisien. Bagaimanapun, rekursi menderita overhead pemanggilan fungsi, yang dalam contoh di atas dapat menjadi substansial dibandingkan dengan operasi di dalam fungsi itu sendiri.

Jadi seluruh alasan untuk melakukan rekursi daripada iterasi harus memanfaatkan tumpukan panggilan untuk melakukan beberapa hal pintar. Misalnya, jika Anda memanggil suatu fungsi beberapa kali dengan parameter berbeda di dalam loop yang sama, itulah cara untuk menyelesaikan percabangan . Contoh klasik adalah segitiga Sierpinski .

Anda dapat menggambar salah satunya dengan sangat sederhana dengan rekursi, di mana tumpukan panggilan bercabang dalam 3 arah:

private void BuildVertices(double x, double y, double len)
{
    if (len > 0.002)
    {
        mesh.Positions.Add(new Point3D(x, y + len, -len));
        mesh.Positions.Add(new Point3D(x - len, y - len, -len));
        mesh.Positions.Add(new Point3D(x + len, y - len, -len));
        len *= 0.5;
        BuildVertices(x, y + len, len);
        BuildVertices(x - len, y - len, len);
        BuildVertices(x + len, y - len, len);
    }
}

Jika Anda mencoba melakukan hal yang sama dengan iterasi, saya pikir Anda akan menemukan bahwa dibutuhkan lebih banyak kode untuk diselesaikan.

Kasus penggunaan umum lainnya mungkin termasuk melintasi hierarki, misalnya perayap situs web, perbandingan direktori, dll.

Kesimpulan

Dalam istilah praktis, rekursi paling masuk akal kapan pun Anda membutuhkan percabangan berulang.

Rekursi adalah metode pemecahan masalah berdasarkan mentalitas membagi dan menaklukkan. Ide dasarnya adalah Anda mengambil masalah asli dan membaginya menjadi instance yang lebih kecil (lebih mudah diselesaikan) dari dirinya sendiri, menyelesaikan instance yang lebih kecil tersebut (biasanya dengan menggunakan algoritme yang sama lagi) dan kemudian menyusunnya kembali ke dalam solusi akhir.

Contoh kanonik adalah rutin untuk menghasilkan Faktorial n. Faktorial n dihitung dengan mengalikan semua angka antara 1 dan n. Solusi berulang di C # terlihat seperti ini:

public int Fact(int n)
{
  int fact = 1;

  for( int i = 2; i <= n; i++)
  {
    fact = fact * i;
  }

  return fact;
}

Tidak ada yang mengejutkan tentang solusi berulang dan harus masuk akal bagi siapa pun yang akrab dengan C #.

Solusi rekursif ditemukan dengan mengetahui bahwa Faktorial ke-n adalah n * Fakta (n-1). Atau dengan kata lain, jika Anda mengetahui bilangan Faktorial tertentu, Anda dapat menghitung bilangan berikutnya. Berikut adalah solusi rekursif di C #:

public int FactRec(int n)
{
  if( n < 2 )
  {
    return 1;
  }

  return n * FactRec( n - 1 );
}

Bagian pertama dari fungsi ini dikenal sebagai Kasus Dasar (atau terkadang Klausa Penjaga) dan mencegah algoritme agar tidak berjalan selamanya. Itu hanya mengembalikan nilai 1 setiap kali fungsi dipanggil dengan nilai 1 atau kurang. Bagian kedua lebih menarik dan dikenal sebagai Langkah Rekursif . Di sini kita memanggil metode yang sama dengan parameter yang sedikit dimodifikasi (kita menguranginya dengan 1) dan kemudian mengalikan hasilnya dengan salinan n kita.

Saat pertama kali ditemui, ini bisa agak membingungkan sehingga instruktif untuk memeriksa cara kerjanya saat dijalankan. Bayangkan kita memanggil FactRec (5). Kami memasuki rutinitas, tidak diambil oleh kasus dasar dan jadi kami berakhir seperti ini:

// In FactRec(5)
return 5 * FactRec( 5 - 1 );

// which is
return 5 * FactRec(4);

Jika kita memasukkan kembali metode dengan parameter 4, kita lagi-lagi tidak dihentikan oleh klausa penjaga sehingga kita berakhir di:

// In FactRec(4)
return 4 * FactRec(3);

Jika kita mengganti nilai pengembalian ini ke nilai pengembalian di atas yang kita dapatkan

// In FactRec(5)
return 5 * (4 * FactRec(3));

Ini akan memberi Anda petunjuk tentang bagaimana solusi akhir dicapai sehingga kami akan mempercepat dan menunjukkan setiap langkah dalam perjalanan ke bawah:

return 5 * (4 * FactRec(3));
return 5 * (4 * (3 * FactRec(2)));
return 5 * (4 * (3 * (2 * FactRec(1))));
return 5 * (4 * (3 * (2 * (1))));

Substitusi terakhir itu terjadi ketika kasus dasar dipicu. Pada titik ini kita memiliki rumus algrabar sederhana untuk dipecahkan yang sederhananya sama dengan definisi Faktorial.

Penting untuk dicatat bahwa setiap panggilan ke dalam metode menghasilkan kasus dasar yang dipicu atau panggilan ke metode yang sama di mana parameter lebih dekat dengan kasus dasar (sering disebut panggilan rekursif). Jika tidak demikian maka metode ini akan berjalan selamanya.

Rekursi memecahkan masalah dengan fungsi yang memanggil dirinya sendiri. Contoh yang bagus dari ini adalah fungsi faktorial. Faktorial adalah masalah matematika di mana faktorial dari 5, misalnya, adalah 5 * 4 * 3 * 2 * 1. Fungsi ini menyelesaikannya di C # untuk bilangan bulat positif (tidak diuji - mungkin ada bug).

public int Factorial(int n)
{
    if (n <= 1)
        return 1;

    return n * Factorial(n - 1);
}

Rekursi mengacu pada metode yang memecahkan masalah dengan memecahkan versi masalah yang lebih kecil dan kemudian menggunakan hasil tersebut ditambah beberapa perhitungan lain untuk merumuskan jawaban dari masalah asli. Seringkali, dalam proses menyelesaikan versi yang lebih kecil, metode akan menyelesaikan versi masalah yang lebih kecil, dan seterusnya, hingga mencapai "kasus dasar" yang sepele untuk dipecahkan.

Misalnya, untuk menghitung faktorial untuk bilangan tersebut X, seseorang dapat merepresentasikannya sebagai X times the factorial of X-1. Jadi, metode "berulang" untuk mencari faktorial X-1, dan kemudian mengalikan apa pun yang didapat Xuntuk memberikan jawaban akhir. Tentu saja, untuk mencari faktorialnya X-1, terlebih dahulu dihitung faktorialnya X-2, dan seterusnya. Kasus dasarnya adalah ketika X0 atau 1, dalam hal ini ia tahu untuk kembali 1sejak 0! = 1! = 1.

Pertimbangkan masalah lama yang terkenal :

Dalam matematika, pembagi persekutuan terbesar (gcd)… dari dua atau lebih bilangan bulat bukan nol, adalah bilangan bulat positif terbesar yang membagi bilangan tanpa sisa.

Definisi dari gcd sangat sederhana:

dimana mod adalah operator modulo (yaitu, sisa setelah pembagian integer).

Dalam bahasa Inggris, definisi ini mengatakan pembagi persekutuan terbesar dari semua bilangan dan nol adalah bilangan itu, dan pembagi persekutuan terbesar dari dua bilangan m dan n adalah pembagi persekutuan terbesar dari n dan sisa setelah membagi m dengan n .

Jika Anda ingin tahu mengapa ini berhasil, lihat artikel Wikipedia tentang algoritma Euclidean .

Mari kita hitung gcd (10, 8) sebagai contoh. Setiap langkah sama dengan yang sebelumnya:

1. gcd (10, 8)
2. gcd (10, 10 mod 8)
3. gcd (8, 2)
4. gcd (8, 8 mod 2)
5. gcd (2, 0)
6. 2

Pada langkah pertama, 8 tidak sama dengan nol, jadi definisi bagian kedua berlaku. 10 mod 8 = 2 karena 8 masuk ke 10 sekali dengan sisa 2. Pada langkah 3, bagian kedua berlaku lagi, tapi kali ini 8 mod 2 = 0 karena 2 membagi 8 tanpa sisa. Pada langkah 5, argumen kedua adalah 0, jadi jawabannya adalah 2.

Apakah Anda memperhatikan bahwa gcd muncul di sisi kiri dan kanan dari tanda sama dengan? Seorang ahli matematika akan mengatakan definisi ini rekursif karena ekspresi yang Anda definisikan berulang di dalam definisinya.

Definisi rekursif cenderung elegan. Misalnya, definisi rekursif untuk penjumlahan daftar adalah

sum l =
    if empty(l)
        return 0
    else
        return head(l) + sum(tail(l))

di mana headelemen pertama dalam daftar dan tailsisa daftar. Perhatikan bahwa sumberulang dalam definisinya di bagian akhir.

Mungkin Anda lebih suka nilai maksimum dalam daftar:

max l =
    if empty(l)
        error
    elsif length(l) = 1
        return head(l)
    else
        tailmax = max(tail(l))
        if head(l) > tailmax
            return head(l)
        else
            return tailmax

Anda dapat mendefinisikan perkalian bilangan bulat non-negatif secara rekursif untuk mengubahnya menjadi serangkaian penambahan:

a * b =
    if b = 0
        return 0
    else
        return a + (a * (b - 1))

Jika sedikit tentang mengubah perkalian menjadi serangkaian penjumlahan tidak masuk akal, coba kembangkan beberapa contoh sederhana untuk melihat cara kerjanya.

Merge sort memiliki definisi rekursif yang bagus:

sort(l) =
    if empty(l) or length(l) = 1
        return l
    else
        (left,right) = split l
        return merge(sort(left), sort(right))

Definisi rekursif ada di mana-mana jika Anda tahu apa yang harus dicari. Perhatikan bagaimana semua definisi ini memiliki kasus dasar yang sangat sederhana, misalnya , gcd (m, 0) = m. Kasus rekursif mengecilkan masalah untuk mendapatkan jawaban yang mudah.

Dengan pemahaman ini, Anda sekarang dapat menghargai algoritme lain di artikel Wikipedia tentang rekursi !

1. Sebuah fungsi yang memanggil dirinya sendiri
2. Ketika suatu fungsi dapat (dengan mudah) diuraikan menjadi operasi sederhana ditambah fungsi yang sama pada beberapa bagian masalah yang lebih kecil. Saya harus mengatakan, sebaliknya, ini membuatnya menjadi kandidat yang baik untuk rekursi.
3. Mereka melakukannya!

Contoh kanonik adalah faktorial yang terlihat seperti:

int fact(int a) 
{
  if(a==1)
    return 1;

  return a*fact(a-1);
}

Secara umum, rekursi tidak selalu cepat (overhead panggilan fungsi cenderung tinggi karena fungsi rekursif cenderung kecil, lihat di atas) dan dapat mengalami beberapa masalah (siapa saja yang menumpuk?). Beberapa orang mengatakan mereka cenderung sulit mendapatkan 'hak' dalam kasus-kasus yang tidak sepele, tetapi saya tidak benar-benar mempercayai hal itu. Dalam beberapa situasi, rekursi paling masuk akal dan merupakan cara paling elegan dan jelas untuk menulis fungsi tertentu. Perlu dicatat bahwa beberapa bahasa mendukung solusi rekursif dan lebih mengoptimalkannya (LISP muncul dalam pikiran).

Fungsi rekursif adalah fungsi yang memanggil dirinya sendiri. Alasan paling umum yang saya temukan untuk menggunakannya adalah melintasi struktur pohon. Misalnya, jika saya memiliki TreeView dengan kotak centang (pikirkan penginstalan program baru, halaman "pilih fitur untuk diinstal"), saya mungkin menginginkan tombol "centang semua" yang akan menjadi seperti ini (kode-p):

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

function checkRecursively(Node n) {
    n.Checked = True;
    foreach ( n.Children as child ) {
        checkRecursively(child);
    }
}

Jadi Anda dapat melihat bahwa checkRecursively pertama-tama memeriksa node yang diteruskannya, lalu memanggil dirinya sendiri untuk setiap turunan node tersebut.

Anda harus sedikit berhati-hati dengan rekursi. Jika Anda masuk ke loop rekursif tak terbatas, Anda akan mendapatkan pengecualian Stack Overflow :)

Saya tidak dapat memikirkan alasan mengapa orang tidak boleh menggunakannya, jika perlu. Ini berguna dalam beberapa keadaan, dan tidak dalam keadaan lain.

Saya pikir karena ini adalah teknik yang menarik, beberapa pembuat kode mungkin akhirnya menggunakannya lebih sering daripada yang seharusnya, tanpa pembenaran yang nyata. Ini telah memberikan rekursi nama yang buruk di beberapa kalangan.

Rekursi adalah ekspresi yang secara langsung atau tidak langsung merujuk dirinya sendiri.

Pertimbangkan akronim rekursif sebagai contoh sederhana:

• GNU adalah singkatan dari GNU's Not Unix
• PHP adalah singkatan dari PHP: Hypertext Preprocessor
• YAML adalah singkatan dari YAML Ain't Markup Language
• WINE adalah singkatan dari Wine Is Not an Emulator
• VISA adalah singkatan dari Visa International Service Association

Lebih banyak contoh di Wikipedia

Rekursi bekerja paling baik dengan apa yang saya suka sebut "masalah fraktal", di mana Anda berurusan dengan hal besar yang terbuat dari versi yang lebih kecil dari benda besar itu, yang masing-masing merupakan versi yang lebih kecil dari benda besar itu, dan seterusnya. Jika Anda pernah harus melintasi atau mencari sesuatu seperti pohon atau struktur identik bersarang, Anda punya masalah yang mungkin bisa menjadi kandidat yang baik untuk rekursi.

Orang menghindari rekursi karena sejumlah alasan:

1. Kebanyakan orang (termasuk saya) memotong gigi pemrograman mereka pada pemrograman prosedural atau berorientasi objek sebagai lawan pemrograman fungsional. Bagi orang seperti itu, pendekatan berulang (biasanya menggunakan loop) terasa lebih alami.

2. Bagi kita yang memotong gigi pemrograman pada pemrograman prosedural atau berorientasi objek sering diberitahu untuk menghindari rekursi karena rawan kesalahan.

3. Kami sering diberi tahu bahwa rekursi lambat. Memanggil dan kembali dari rutinitas berulang kali melibatkan banyak tumpukan mendorong dan bermunculan, yang lebih lambat daripada perulangan. Saya pikir beberapa bahasa menangani ini lebih baik daripada yang lain, dan bahasa-bahasa itu kemungkinan besar bukan bahasa yang paradigma dominannya prosedural atau berorientasi objek.

4. Setidaknya untuk beberapa bahasa pemrograman yang saya gunakan, saya ingat pernah mendengar rekomendasi untuk tidak menggunakan rekursi jika melampaui kedalaman tertentu karena tumpukannya tidak terlalu dalam.

Pernyataan rekursif adalah pernyataan di mana Anda mendefinisikan proses apa yang harus dilakukan selanjutnya sebagai kombinasi dari masukan dan apa yang telah Anda lakukan.

Misalnya, ambil faktorial:

factorial(6) = 6*5*4*3*2*1

Tetapi mudah untuk melihat faktorial (6) juga adalah:

6 * factorial(5) = 6*(5*4*3*2*1).

Jadi secara umum:

factorial(n) = n*factorial(n-1)

Tentu saja, hal rumit tentang rekursi adalah jika Anda ingin mendefinisikan hal-hal dalam kaitannya dengan apa yang telah Anda lakukan, perlu ada tempat untuk memulai.

Dalam contoh ini, kita hanya membuat kasus khusus dengan mendefinisikan faktorial (1) = 1.

Sekarang kita melihatnya dari bawah ke atas:

factorial(6) = 6*factorial(5)
                   = 6*5*factorial(4)
                   = 6*5*4*factorial(3) = 6*5*4*3*factorial(2) = 6*5*4*3*2*factorial(1) = 6*5*4*3*2*1

Karena kita mendefinisikan faktorial (1) = 1, kita mencapai "bawah".

Secara umum, prosedur rekursif memiliki dua bagian:

1) Bagian rekursif, yang mendefinisikan beberapa prosedur dalam kaitannya dengan masukan baru yang dikombinasikan dengan apa yang telah Anda "lakukan" melalui prosedur yang sama. (yaitu factorial(n) = n*factorial(n-1))

2) Bagian dasar, yang memastikan bahwa proses tidak berulang selamanya dengan memberinya tempat untuk memulai (mis factorial(1) = 1 )

Mungkin agak membingungkan untuk memahami pada awalnya, tetapi lihat saja beberapa contoh dan semuanya harus bersatu. Jika Anda ingin pemahaman konsep yang lebih dalam, pelajari induksi matematika. Juga, ketahuilah bahwa beberapa bahasa mengoptimalkan panggilan rekursif sementara yang lain tidak. Sangat mudah untuk membuat fungsi rekursif yang sangat lambat jika Anda tidak berhati-hati, tetapi ada juga teknik untuk membuatnya bekerja dalam banyak kasus.

Semoga ini membantu...

Saya suka definisi ini:
Dalam rekursi, sebuah rutinitas memecahkan sebagian kecil dari masalah itu sendiri, membagi masalah menjadi bagian-bagian yang lebih kecil, dan kemudian memanggil dirinya sendiri untuk menyelesaikan setiap bagian yang lebih kecil.

Saya juga menyukai diskusi Steve McConnells tentang rekursi di Code Complete di mana dia mengkritik contoh yang digunakan dalam buku Ilmu Komputer tentang Rekursi.

Jangan gunakan rekursi untuk faktorial atau bilangan Fibonacci

Satu masalah dengan buku teks ilmu komputer adalah bahwa mereka menyajikan contoh rekursi yang konyol. Contoh tipikal adalah menghitung faktorial atau menghitung deret Fibonacci. Rekursi adalah alat yang ampuh, dan sangat bodoh menggunakannya dalam salah satu kasus tersebut. Jika seorang programmer yang bekerja untuk saya menggunakan rekursi untuk menghitung faktorial, saya akan mempekerjakan orang lain.

Saya pikir ini adalah poin yang sangat menarik untuk diangkat dan mungkin menjadi alasan mengapa rekursi sering disalahpahami.

EDIT: Ini bukan penggalian di jawaban Dav - saya belum melihat balasan itu ketika saya memposting ini

1.) Suatu metode bersifat rekursif jika dapat memanggil dirinya sendiri; baik secara langsung:

void f() {
   ... f() ... 
}

atau secara tidak langsung:

void f() {
    ... g() ...
}

void g() {
   ... f() ...
}

2.) Kapan menggunakan rekursi

Q: Does using recursion usually make your code faster? 
A: No.
Q: Does using recursion usually use less memory? 
A: No.
Q: Then why use recursion? 
A: It sometimes makes your code much simpler!

3.) Orang menggunakan rekursi hanya jika menulis kode iteratif sangat rumit. Misalnya, teknik penjelajahan pohon seperti preorder, postorder dapat dibuat secara iteratif dan rekursif. Tetapi biasanya kita menggunakan rekursif karena kesederhanaannya.

Berikut contoh sederhana: berapa banyak elemen dalam satu set. (ada cara yang lebih baik untuk menghitung sesuatu, tetapi ini adalah contoh rekursif sederhana yang bagus.)

Pertama, kita membutuhkan dua aturan:

1. jika set kosong, jumlah item dalam set adalah nol (duh!).
2. jika set tidak kosong, hitungannya satu ditambah jumlah item dalam set setelah satu item dihapus.

Misalkan Anda memiliki set seperti ini: [xxx]. mari kita hitung berapa banyak item yang ada.

1. setnya adalah [xxx] yang tidak kosong, jadi kami menerapkan aturan 2. jumlah item adalah satu ditambah jumlah item di [xx] (yaitu kami menghapus item).
2. setnya adalah [xx], jadi kami menerapkan aturan 2 lagi: satu + jumlah item di [x].
3. setnya adalah [x], yang masih cocok dengan aturan 2: satu + jumlah item di [].
4. Sekarang setnya adalah [], yang cocok dengan aturan 1: hitungannya nol!
5. Sekarang kita tahu jawabannya di langkah 4 (0), kita bisa menyelesaikan langkah 3 (1 + 0)
6. Demikian juga, sekarang setelah kita mengetahui jawabannya di langkah 3 (1), kita dapat menyelesaikan langkah 2 (1 + 1)
7. Dan akhirnya sekarang kita tahu jawabannya di langkah 2 (2), kita bisa menyelesaikan langkah 1 (1 + 2) dan mendapatkan hitungan item di [xxx], yaitu 3. Hore!

Kami dapat mewakili ini sebagai:

count of [x x x] = 1 + count of [x x]
                 = 1 + (1 + count of [x])
                 = 1 + (1 + (1 + count of []))
                 = 1 + (1 + (1 + 0)))
                 = 1 + (1 + (1))
                 = 1 + (2)
                 = 3

Saat menerapkan solusi rekursif, Anda biasanya memiliki setidaknya 2 aturan:

• dasar, kasus sederhana yang menyatakan apa yang terjadi ketika Anda telah "menggunakan" semua data Anda. Ini biasanya merupakan variasi dari "jika Anda kehabisan data untuk diproses, jawaban Anda adalah X"
• aturan rekursif, yang menyatakan apa yang terjadi jika Anda masih memiliki data. Ini biasanya semacam aturan yang mengatakan "lakukan sesuatu untuk membuat kumpulan data Anda lebih kecil, dan terapkan kembali aturan Anda ke kumpulan data yang lebih kecil".

Jika kita menerjemahkan di atas ke pseudocode, kita mendapatkan:

numberOfItems(set)
    if set is empty
        return 0
    else
        remove 1 item from set
        return 1 + numberOfItems(set)

Ada lebih banyak contoh berguna (melintasi pohon, misalnya) yang saya yakin akan dibahas orang lain.

Nah, itu definisi yang cukup baik yang Anda miliki. Dan wikipedia memiliki definisi yang bagus juga. Jadi saya akan menambahkan definisi lain (mungkin lebih buruk) untuk Anda.

Ketika orang merujuk ke "rekursi", mereka biasanya berbicara tentang fungsi yang telah mereka tulis yang memanggil dirinya sendiri berulang kali hingga selesai dengan tugasnya. Rekursi dapat membantu saat melintasi hierarki dalam struktur data.

Contoh: Definisi rekursif dari tangga adalah: Tangga terdiri dari: - satu anak tangga dan satu tangga (rekursi) - atau hanya satu langkah (terminasi)

Untuk mengulangi masalah yang sudah dipecahkan: jangan lakukan apa pun, Anda sudah selesai.
Untuk mengulangi masalah terbuka: lakukan langkah berikutnya, lalu ulangi masalah lainnya.

Dalam bahasa Inggris sederhana: Asumsikan Anda dapat melakukan 3 hal:

1. Ambil satu apel
2. Tuliskan nilai penghitungan
3. Hitung tanda penghitungan

Anda memiliki banyak apel di depan Anda di atas meja dan Anda ingin tahu berapa banyak apel itu.

start
  Is the table empty?
  yes: Count the tally marks and cheer like it's your birthday!
  no:  Take 1 apple and put it aside
       Write down a tally mark
       goto start

Proses pengulangan hal yang sama sampai Anda selesai disebut rekursi.

Saya harap ini adalah jawaban "bahasa Inggris biasa" yang Anda cari!

Fungsi rekursif adalah fungsi yang berisi panggilan ke dirinya sendiri. Struct rekursif adalah struct yang berisi turunannya sendiri. Anda dapat menggabungkan keduanya sebagai kelas rekursif. Bagian penting dari item rekursif adalah ia berisi instance / panggilan itu sendiri.

Pertimbangkan dua cermin yang saling berhadapan. Kami telah melihat efek tak terhingga rapi yang mereka buat. Setiap refleksi adalah turunan dari cermin, yang terkandung dalam cermin lain, dll. Cermin yang berisi refleksi itu sendiri adalah rekursi.

Sebuah pohon pencarian biner adalah contoh pemrograman yang baik rekursi. Strukturnya rekursif dengan setiap Node berisi 2 instance Node. Fungsi untuk bekerja pada pohon pencarian biner juga bersifat rekursif.

Ini adalah pertanyaan lama, tapi saya ingin menambahkan jawaban dari sudut pandang logistik (yaitu bukan dari sudut pandang ketepatan algoritma atau sudut pandang kinerja).

Saya menggunakan Java untuk bekerja, dan Java tidak mendukung fungsi bersarang. Dengan demikian, jika saya ingin melakukan rekursi, saya mungkin harus menentukan fungsi eksternal (yang ada hanya karena kode saya bertentangan dengan aturan birokrasi Java), atau saya mungkin harus merefaktor kode sama sekali (yang sangat saya benci melakukannya).

Jadi, saya sering menghindari rekursi, dan menggunakan operasi tumpukan sebagai gantinya, karena rekursi itu sendiri pada dasarnya adalah operasi tumpukan.

Anda ingin menggunakannya kapan pun Anda memiliki struktur pohon. Ini sangat berguna dalam membaca XML.

Rekursi seperti yang berlaku untuk pemrograman pada dasarnya memanggil fungsi dari dalam definisinya sendiri (di dalam dirinya sendiri), dengan parameter yang berbeda untuk menyelesaikan tugas.

"Jika saya memiliki palu, buatlah semuanya terlihat seperti paku."

Rekursi adalah strategi pemecahan masalah yang sangat besar masalah , di mana pada setiap langkahnya, "ubah 2 hal kecil menjadi satu hal yang lebih besar", setiap kali dengan palu yang sama.

Contoh

Misalkan meja Anda ditutupi dengan 1024 kertas yang berantakan. Bagaimana Anda membuat satu tumpukan kertas yang rapi dan bersih dari kekacauan, menggunakan rekursi?

1. Bagi: Sebarkan semua lembar, jadi Anda hanya memiliki satu lembar di setiap "tumpukan".
2. Menaklukkan:
   2. Berkelilinglah, letakkan setiap lembar di atas satu lembar lainnya. Anda sekarang memiliki tumpukan 2.
   3. Berkelilinglah, letakkan setiap 2 tumpukan di atas 2 tumpukan lainnya. Anda sekarang memiliki tumpukan 4.
   4. Berkelilinglah, letakkan setiap 4 tumpukan di atas 4 tumpukan lainnya. Anda sekarang memiliki tumpukan 8.
   5. ... terus menerus ...
   6. Anda sekarang memiliki satu tumpukan besar 1024 lembar!

Perhatikan bahwa ini cukup intuitif, selain menghitung semuanya (yang tidak sepenuhnya diperlukan). Anda mungkin tidak akan turun ke tumpukan 1 lembar, pada kenyataannya, tetapi Anda bisa dan itu akan tetap berfungsi. Bagian yang penting adalah palu: Dengan tangan Anda, Anda selalu dapat meletakkan satu tumpukan di atas yang lain untuk membuat tumpukan yang lebih besar, dan tidak masalah (dalam alasan) seberapa besar tumpukan tersebut.

Rekursi adalah proses di mana metode memanggil dirinya sendiri untuk dapat melakukan tugas tertentu. Ini mengurangi redundensi kode. Kebanyakan fungsi atau metode rekursif harus memiliki kondisi untuk menghentikan panggilan rekursif, yaitu menghentikan panggilan itu sendiri jika kondisi terpenuhi - ini mencegah pembuatan loop tak terbatas. Tidak semua fungsi cocok untuk digunakan secara rekursif.

hei, maaf jika pendapat saya setuju dengan seseorang, saya hanya mencoba menjelaskan rekursi dalam bahasa Inggris yang sederhana.

misalkan Anda memiliki tiga manajer - Jack, John dan Morgan. Jack mengelola 2 programmer, John - 3, dan Morgan - 5. Anda akan memberi setiap manajer $ 300 dan ingin tahu berapa biayanya. Jawabannya jelas - tetapi bagaimana jika 2 karyawan Morgan juga menjadi manajer?

DI SINI datang rekursi. Anda mulai dari atas hierarki. biaya musim panas adalah $ 0. Anda mulai dengan Jack, Kemudian periksa apakah dia memiliki manajer sebagai karyawan. jika Anda menemukan salah satu dari mereka, periksa apakah mereka memiliki manajer sebagai karyawan dan sebagainya. Tambahkan $ 300 ke biaya musim panas setiap kali Anda menemukan manajer. setelah Anda selesai dengan Jack, pergi ke John, karyawannya dan kemudian ke Morgan.

Anda tidak akan pernah tahu, berapa siklus yang akan Anda jalani sebelum mendapatkan jawaban, meskipun Anda tahu berapa banyak manajer yang Anda miliki dan berapa Anggaran yang dapat Anda belanjakan.

Rekursi adalah pohon, dengan cabang dan daun, masing-masing disebut orang tua dan anak. Saat Anda menggunakan algoritme rekursi, Anda kurang lebih secara sadar sedang membangun pohon dari data.

Dalam bahasa Inggris yang sederhana, rekursi berarti mengulang sesuatu lagi dan lagi.

Dalam pemrograman salah satu contohnya adalah memanggil fungsi di dalam dirinya sendiri.

Perhatikan contoh penghitungan faktorial bilangan berikut:

public int fact(int n)
{
    if (n==0) return 1;
    else return n*fact(n-1)
}

Algoritme apa pun menunjukkan rekursi struktural pada tipe data jika pada dasarnya terdiri dari pernyataan sakelar dengan kasus untuk setiap kasus tipe data.

misalnya, saat Anda mengerjakan sebuah tipe

  tree = null 
       | leaf(value:integer) 
       | node(left: tree, right:tree)

algoritma rekursif struktural akan memiliki bentuk

 function computeSomething(x : tree) =
   if x is null: base case
   if x is leaf: do something with x.value
   if x is node: do something with x.left,
                 do something with x.right,
                 combine the results

ini benar-benar cara paling jelas untuk menulis algoritme apa pun yang berfungsi pada struktur data.

sekarang, ketika Anda melihat bilangan bulat (baik, bilangan asli) seperti yang didefinisikan menggunakan aksioma Peano

 integer = 0 | succ(integer)

Anda melihat bahwa algoritma rekursif struktural pada bilangan bulat terlihat seperti ini

 function computeSomething(x : integer) =
   if x is 0 : base case
   if x is succ(prev) : do something with prev

fungsi faktorial yang terlalu terkenal adalah tentang contoh paling remeh dari bentuk ini.

fungsi memanggil dirinya sendiri atau menggunakan definisinya sendiri.