Kapan harus menggunakan rekursi?

Kapan beberapa (relatif) dasar (pikirkan siswa CS tingkat perguruan tinggi tahun pertama) ketika seseorang akan menggunakan rekursi alih-alih hanya satu lingkaran?

Saya telah mengajar C ++ kepada mahasiswa sarjana selama sekitar dua tahun dan membahas rekursi. Dari pengalaman saya, pertanyaan dan perasaan Anda sangat umum. Pada ekstrem, beberapa siswa melihat rekursi sebagai hal yang sulit dipahami sementara yang lain ingin menggunakannya untuk hampir semua hal.

Saya pikir Dave meringkaskannya dengan baik: gunakan di tempat yang sesuai. Artinya, gunakan saat terasa alami. Ketika Anda menghadapi masalah di mana itu cocok dengan baik, Anda kemungkinan besar akan mengenalinya: sepertinya Anda bahkan tidak bisa datang dengan solusi berulang. Juga, kejelasan adalah aspek penting dari pemrograman. Orang lain (dan Anda juga!) Harus dapat membaca dan memahami kode yang Anda hasilkan. Saya pikir aman untuk mengatakan loop berulang lebih mudah dipahami pada pandangan pertama daripada rekursi.

Saya tidak tahu seberapa baik Anda mengetahui pemrograman atau ilmu komputer secara umum, tetapi saya merasa sangat tidak masuk akal untuk berbicara tentang fungsi virtual, warisan atau tentang konsep lanjutan apa pun di sini. Saya sering memulai dengan contoh klasik penghitungan angka Fibonacci. Cocok di sini dengan baik, karena angka-angka Fibonacci ditentukan secara rekursif . Hal ini mudah dimengerti dan tidak memerlukan setiap mewah fitur bahasa. Setelah siswa mendapatkan beberapa pemahaman dasar tentang rekursi, kami telah melihat lagi beberapa fungsi sederhana yang telah kami bangun sebelumnya. Ini sebuah contoh:

Apakah string berisi karakter ?$x$

Ini adalah bagaimana kami melakukannya sebelumnya: iterate the string, dan lihat apakah ada indeks yang berisi .$x$

bool find(const std::string& s, char x)
{
   for(int i = 0; i < s.size(); ++i)
   {
      if(s[i] == x)
         return true;
   }

   return false;
}

Pertanyaannya adalah, bisakah kita melakukannya secara rekursif? Tentu kami bisa, ini salah satu caranya:

bool find(const std::string& s, int idx, char x)
{
   if(idx == s.size())
      return false;

   return s[idx] == x || find(s, ++idx);
}

Pertanyaan alami selanjutnya adalah, haruskah kita melakukannya seperti ini? Mungkin tidak. Mengapa? Lebih sulit untuk dipahami dan lebih sulit untuk dibuat. Karena itu lebih rentan terhadap kesalahan juga.

Solusi untuk beberapa masalah lebih alami diungkapkan dengan menggunakan rekursi.

Misalnya, asumsikan bahwa Anda memiliki struktur data pohon dengan dua jenis node: daun, yang menyimpan nilai integer; dan cabang, yang memiliki subtree kiri dan kanan di bidangnya. Asumsikan daun dipesan, sehingga nilai terendah ada di daun paling kiri.

Misalkan tugasnya adalah mencetak nilai pohon secara berurutan. Algoritma rekursif untuk melakukan ini cukup alami:

class Node { abstract void traverse(); }
class Leaf extends Node { 
  int val; 
  void traverse() { print(val); }
} 
class Branch extends Node {
  Node left, right;
  void traverse() { left.traverse(); right.traverse(); }
}

Menulis kode yang setara tanpa rekursi akan jauh lebih sulit. Cobalah!

Secara umum, rekursi bekerja dengan baik untuk algoritma pada struktur data rekursif seperti pohon, atau untuk masalah yang secara alami dapat dipecah menjadi sub-masalah. Lihat, misalnya, bagilah dan taklukkan algoritma .

Jika Anda benar-benar ingin melihat rekursi di lingkungannya yang paling alami, maka Anda harus melihat bahasa pemrograman fungsional seperti Haskell. Dalam bahasa seperti itu, tidak ada konstruk perulangan, jadi semuanya diekspresikan menggunakan rekursi (atau fungsi tingkat tinggi, tapi itu cerita lain, satu yang perlu diketahui juga).

Perhatikan juga bahwa bahasa pemrograman fungsional melakukan rekursi ekor yang dioptimalkan. Ini berarti bahwa mereka tidak meletakkan bingkai tumpukan kecuali mereka tidak perlu --- pada dasarnya, rekursi dapat dikonversi ke loop. Dari perspektif praktis, Anda dapat menulis kode dengan cara alami, tetapi mendapatkan kinerja kode iteratif. Sebagai catatan, tampaknya kompiler C ++ juga mengoptimalkan panggilan ekor , sehingga tidak ada overhead tambahan menggunakan rekursi dalam C ++.

Dari seseorang yang secara praktis hidup dalam rekursi, saya akan mencoba dan menjelaskan masalah ini.

Ketika pertama kali diperkenalkan untuk rekursi Anda belajar bahwa itu adalah fungsi yang memanggil dirinya sendiri dan pada dasarnya ditunjukkan dengan algoritma seperti tree traversal. Kemudian Anda menemukan bahwa itu banyak digunakan dalam pemrograman fungsional untuk bahasa seperti LISP dan F #. Dengan F # I menulis, sebagian besar dari apa yang saya tulis adalah rekursif dan pencocokan pola.

Jika Anda mempelajari lebih lanjut tentang pemrograman fungsional seperti F # Anda akan belajar F # Daftar diimplementasikan sebagai daftar yang terhubung sendiri, yang berarti bahwa operasi yang mengakses hanya kepala daftar adalah O (1), dan akses elemen adalah O (n). Setelah Anda mempelajari ini, Anda cenderung untuk menelusuri data sebagai daftar, membangun daftar baru dalam urutan terbalik dan kemudian membalik daftar sebelum kembali dari fungsi yang sangat efektif.

Sekarang jika Anda mulai memikirkan hal ini, Anda segera menyadari bahwa fungsi rekursif akan mendorong bingkai tumpukan setiap kali panggilan fungsi dibuat dan dapat menyebabkan tumpukan meluap. Namun, jika Anda membangun fungsi rekursif Anda sehingga dapat melakukan panggilan ekor dan kompiler mendukung kemampuan untuk mengoptimalkan kode untuk panggilan ekor. yaitu .NET OpCodes.Tailcall Field Anda tidak akan menyebabkan stack overflow. Pada titik ini Anda mulai menulis perulangan apa pun sebagai fungsi rekursif, dan keputusan apa pun sebagai kecocokan; hari-hari ifdan whilesekarang sejarah.

Setelah Anda pindah ke AI menggunakan backtracking dalam bahasa seperti PROLOG, maka semuanya bersifat rekursif. Walaupun ini memerlukan pemikiran dengan cara yang sangat berbeda dari kode imperatif, jika PROLOG adalah alat yang tepat untuk masalah ini, itu membebaskan Anda dari beban harus menulis banyak baris kode, dan dapat mengurangi jumlah kesalahan secara dramatis. Lihat: Pelanggan Amzi eoTek

Untuk kembali ke pertanyaan Anda tentang kapan harus menggunakan rekursi; satu cara saya melihat pemrograman adalah dengan perangkat keras di satu ujung dan konsep abstrak di ujung lainnya. Semakin dekat ke perangkat keras masalah semakin saya berpikir dalam bahasa imperatif ifdan while, semakin abstrak masalahnya, semakin saya berpikir dalam bahasa tingkat tinggi dengan rekursi. Namun, jika Anda mulai menulis kode sistem tingkat rendah dan semacamnya, dan Anda ingin memverifikasi itu valid, Anda kemudian menemukan solusi seperti pembuktian teorema berguna, yang sangat bergantung pada rekursi.

Jika Anda melihat Jane Street, Anda akan melihat mereka menggunakan bahasa fungsional OCaml . Sementara saya belum melihat kode mereka, dari membaca tentang apa yang mereka sebutkan tentang kode mereka, mereka bermuka masam berpikir secara rekursif.

EDIT

Karena Anda mencari daftar penggunaan, saya akan memberi Anda ide dasar tentang apa yang harus dicari dalam kode dan daftar penggunaan dasar yang sebagian besar didasarkan pada konsep Catamorphism yang berada di luar dasar-dasar.

Untuk C ++: Jika Anda mendefinisikan struktur atau kelas yang memiliki pointer ke struktur atau kelas yang sama maka rekursi harus dipertimbangkan untuk metode traversal yang menggunakan pointer.

Kasus sederhana adalah daftar tertaut satu arah. Anda akan memproses daftar mulai dari kepala atau ekor dan kemudian secara rekursif melintasi daftar menggunakan pointer.

Pohon adalah kasus lain di mana rekursi sering digunakan; sedemikian rupa sehingga jika Anda melihat traversal pohon tanpa rekursi Anda harus mulai bertanya mengapa? Itu tidak salah, tetapi sesuatu yang harus dicatat dalam komentar.

Penggunaan rekursi yang umum adalah:

• penyortiran
• mencari
• peta
• melipat
• filter

Untuk memberi Anda kasus penggunaan yang kurang misterius dari yang diberikan dalam jawaban lain: rekursi bercampur sangat baik dengan struktur kelas seperti pohon (Berorientasi Objek) yang berasal dari sumber yang sama. Contoh C ++:

class Expression {
public:
    // The "= 0" means 'I don't implement this, I let my subclasses do that'
    virtual int ComputeValue() = 0;
}

class Plus : public Expression {
private:
    Expression* left
    Expression* right;
public:
    virtual int ComputeValue() { return left->ComputeValue() + right->ComputeValue(); }
}

class Times : public Expression {
private:
    Expression* left
    Expression* right;
public:
    virtual int ComputeValue() { return left->ComputeValue() * right->ComputeValue(); }
}

class Negate : public Expression {
private:
    Expression* expr;
public:
    virtual int ComputeValue() { return -(expr->ComputeValue()); }
}

class Constant : public Expression {
private:
    int value;
public:
    virtual int ComputeValue() { return value; }
}

Contoh di atas menggunakan rekursi: ComputeValue diimplementasikan secara rekursif. Untuk membuat contoh berfungsi, Anda menggunakan fungsi virtual dan pewarisan. Anda tidak tahu persis bagian kiri dan kanan dari kelas Plus, tetapi Anda tidak peduli: itu adalah sesuatu yang dapat menghitung nilainya sendiri, yang perlu Anda ketahui.

Keuntungan penting dari pendekatan di atas adalah bahwa setiap kelas mengurus perhitungannya sendiri . Anda memisahkan implementasi yang berbeda dari setiap sub-ekspresi yang mungkin sepenuhnya: mereka tidak memiliki pengetahuan tentang cara kerja masing-masing. Ini membuat penalaran tentang program lebih mudah dan karena itu membuat program lebih mudah untuk memahami, memelihara, dan memperluas.

Contoh pertama yang digunakan untuk mengajarkan rekursi di kelas pemrograman awal saya adalah fungsi untuk membuat daftar semua digit dalam angka secara terpisah dalam urutan terbalik.

void listDigits(int x){
     if (x <= 0)
        return;
     print x % 10;
     listDigits(x/10);
}

Atau sesuatu seperti itu (saya pergi dari memori di sini dan tidak menguji). Juga, ketika Anda masuk ke kelas tingkat yang lebih tinggi, Anda akan menggunakan banyak rekursi terutama dalam algoritma pencarian, algoritma pengurutan, dll.

Jadi ini mungkin tampak seperti fungsi yang tidak berguna dalam bahasa sekarang, tetapi sangat berguna dalam jangka panjang.