Pertanyaan Contoh fungsi Rekursif [tertutup]


Adakah yang bisa menyarankan contoh pemrograman yang mengilustrasikan fungsi rekursif? Ada kuda-kuda tua yang biasa seperti Deret Fibonacci dan Menara Hanoi, tetapi apa pun selain mereka akan menyenangkan.


31
2017-09-24 12:16


asal


Jawaban:


Ilustrasi ini dalam bahasa Inggris, daripada bahasa pemrograman yang sebenarnya, tetapi berguna untuk menjelaskan proses dengan cara non-teknis:

Seorang anak tidak bisa tidur, jadi ibunya menceritakan tentang seekor katak kecil,
  yang tidak bisa tidur, jadi ibu katak itu menceritakan kisah tentang beruang kecil,
     yang tidak bisa tidur, jadi ibu beruang menceritakan kisah tentang musang kecil
       ... yang tertidur.
     ... dan beruang kecil itu jatuh tertidur;
  ... dan katak kecil tertidur;
... dan anak itu tertidur.

109
2017-09-24 12:20



Untuk memahami  rekursi, pertama-tama kita harus mengerti rekursi.


28
2017-09-24 20:44



Aturan praktis untuk rekursi adalah, "Gunakan rekursi, jika dan hanya jika pada setiap iterasi tugas Anda dibagi menjadi dua atau lebih tugas serupa ".

Jadi Fibonacci bukanlah contoh aplikasi rekursi yang bagus, sedangkan Hanoi adalah contoh yang bagus.

Jadi sebagian besar contoh rekursi yang baik adalah lintasan pohon dalam berbagai lenyap.

Sebagai contoh: grafik traversal - persyaratan yang dikunjungi node tidak akan pernah dikunjungi lagi secara efektif membuat grafik sebuah pohon (pohon adalah grafik terhubung tanpa siklus sederhana)

membagi dan menaklukkan algoritma (quick sort, merge sort) - bagian setelah "divide" merupakan simpul anak-anak, "menaklukkan" konstitues ujung dari node induk ke node anak.


16
2018-02-27 11:21



Bagaimana dengan menguji string karena menjadi palindrome?

bool isPalindrome(char* s, int len)
{
  if(len < 2)
    return TRUE;
  else
    return s[0] == s[len-1] && isPalindrome(&s[1], len-2);
}

Tentu saja, Anda bisa melakukannya dengan lebih efisien.


15
2017-09-24 13:42



Menulis sebuah parser keturunan rekursif!


13
2017-09-24 12:19



Pasangan lain dari "tersangka biasa" adalah Quicksort dan MergeSort


10
2017-09-24 12:23



Dari dunia matematika, ada fungsi Ackermann:

Ackermann(m, n)
{
  if(m==0)
    return n+1;
  else if(m>0 && n==0)
    return Ackermann(m-1, 1);
  else if(m>0 && n>0)
    return Ackermann(m-1, Ackermann(m, n-1));
  else
    throw exception; //not defined for negative m or n
}

Itu selalu berakhir, tetapi menghasilkan hasil yang sangat besar bahkan untuk input yang sangat kecil. Ackermann (4, 2), misalnya, mengembalikan 265536 - 3.


8
2017-09-24 13:36



Itu pola desain interpreter adalah contoh yang cukup bagus karena banyak orang tidak melihat rekursi. Kode contoh yang tercantum dalam artikel Wikipedia menggambarkan dengan baik bagaimana ini dapat diterapkan. Namun, pendekatan yang lebih mendasar yang masih mengimplementasikan pola interpreter adalah a ToString fungsi untuk daftar bertingkat:

class List {
    public List(params object[] items) {
        foreach (object o in items)
            this.Add(o);
    }

    // Most of the implementation omitted …
    public override string ToString() {
        var ret = new StringBuilder();
        ret.Append("( ");
        foreach (object o in this) {
            ret.Append(o);
            ret.Append(" ");
        }
        ret.Append(")");
        return ret.ToString();
    }
}

var lst = new List(1, 2, new List(3, 4), new List(new List(5), 6), 7);
Console.WriteLine(lst);
// yields:
// ( 1 2 ( 3 4 ) ( ( 5 ) 6 ) 7 )

(Ya, saya tahu itu tidak mudah untuk menemukan pola interpreter dalam kode di atas jika Anda mengharapkan fungsi yang disebut Eval … Tetapi sungguh, pola penerjemah tidak memberi tahu kami apa fungsi itu disebut atau bahkan apa yang dilakukannya dan buku GoF secara eksplisit mencantumkan hal di atas sebagai contoh dari pola tersebut.)


6
2017-09-24 12:57



Menurut pendapat saya, rekursi baik untuk diketahui, tetapi sebagian besar solusi yang dapat menggunakan rekursi juga dapat dilakukan dengan menggunakan iterasi, dan iterasi jauh lebih efisien.

Yang dikatakan di sini adalah cara rekursif untuk menemukan kontrol dalam pohon bersarang (seperti ASP.NET atau Winforms):

public Control FindControl(Control startControl, string id)
{
      if (startControl.Id == id)
           return startControl

      if (startControl.Children.Count > 0)
      {
           foreach (Control c in startControl.Children)
           {
                return FindControl(c, id);
           }
      }
      return null;
}

6
2017-09-24 13:50



Berikut ini contoh pragmatis dari dunia sistem file. Utilitas ini secara rekursif menghitung file di bawah direktori yang ditentukan. (Aku tidak ingat kenapa, tapi aku sebenarnya membutuhkan sesuatu seperti ini dulu ...)

public static int countFiles(File f) {
    if (f.isFile()){
        return 1;
    }

    // Count children & recurse into subdirs:
    int count = 0;
    File[] files = f.listFiles();
    for (File fileOrDir : files) {
        count += countFiles(fileOrDir);
    }
    return count;
}

(Perhatikan bahwa di Java a File instance dapat mewakili file normal atau direktori. Utilitas ini mengecualikan direktori dari hitungan.)

Contoh dunia nyata yang umum adalah mis. FileUtils.deleteDirectory() dari Commons IO Perpustakaan; lihat Dokumen API & sumber.


6
2018-05-04 13:17