Rekursi tanpa faktorial, angka Fibonacci dll

Hampir setiap artikel yang saya dapat temukan tentang rekursi mencakup contoh-contoh Angka Fibonacci atau Faktorial, yaitu:

1. Matematika
2. Tidak berguna dalam kehidupan nyata

Apakah ada beberapa contoh kode non-matematika yang menarik untuk mengajarkan rekursi?

Saya sedang memikirkan algoritma divide-and-menaklukkan tetapi mereka biasanya melibatkan struktur data yang kompleks.

Struktur direktori / file adalah contoh terbaik dari penggunaan rekursi, karena semua orang memahaminya sebelum Anda mulai, tetapi segala sesuatu yang melibatkan struktur mirip pohon akan berhasil.

void GetAllFilePaths(Directory dir, List<string> paths)
{
    foreach(File file in dir.Files)
    {
        paths.Add(file.Path);
    }

    foreach(Directory subdir in dir.Directories)
    {
        GetAllFilePaths(subdir, paths)
    }
}

List<string> GetAllFilePaths(Directory dir)
{
    List<string> paths = new List<string>();
    GetAllFilePaths(dir, paths);
    return paths;
}

Cari hal-hal yang melibatkan struktur pohon. Sebuah pohon relatif mudah untuk dipahami, dan keindahan solusi rekursif menjadi jauh lebih cepat daripada dengan struktur data linier seperti daftar.

Hal-hal untuk dipikirkan:

• filesystem - pada dasarnya itu adalah pohon; tugas pemrograman yang bagus adalah mengambil semua gambar .jpg di bawah direktori tertentu dan semua subdirektori
• leluhur - diberi silsilah keluarga, temukan jumlah generasi yang harus Anda jalani untuk menemukan leluhur yang sama; atau periksa apakah dua orang di pohon itu berasal dari generasi yang sama; atau periksa apakah dua orang di pohon tersebut dapat menikah secara sah (tergantung yurisdiksi :)
• Dokumen mirip HTML - mengonversi antara representasi serial (teks) dokumen dan pohon DOM; melakukan operasi pada himpunan bagian DOM (bahkan mungkin menerapkan subset xpath?); ...

Ini semua terkait dengan skenario dunia nyata yang sebenarnya, dan semuanya dapat digunakan dalam aplikasi yang memiliki signifikansi dunia nyata.

https://stackoverflow.com/questions/105838/real-world-examples-of-recursion

• memodelkan infeksi menular
• menghasilkan geometri
• manajemen direktori
• penyortiran

https://stackoverflow.com/questions/2085834/how-did-you-practically-use-recursion

• raytracing
• catur
• parsing kode sumber (tata bahasa)

https://stackoverflow.com/questions/4945128/what-is-a-good-example-of-recursion-other-than-generating-a-fibonacci- berikutnyaence

• Pencarian BST
• Menara Hanoi
• pencarian palindrome

https://stackoverflow.com/questions/126756/examples-of-recursive-functions

• Memberikan cerita berbahasa Inggris yang bagus yang menggambarkan rekursi dengan cerita pengantar tidur.

Inilah beberapa masalah yang lebih praktis yang muncul di benak saya:

• Gabungkan Sortir
• Pencarian Biner
• Traversal, Penyisipan dan Penghapusan pada Pohon (sebagian besar digunakan pada aplikasi basis data)
• Generator permutasi
• Pemecah Sudoku (dengan backtracking)
• Pengecekan ejaan (lagi dengan backtracking)
• Analisis sintaks (.eg, program yang mengubah awalan ke notasi postfix)

QuickSort akan menjadi yang pertama yang terlintas dalam pikiran. Pencarian biner juga merupakan masalah rekursif. Di luar itu, ada seluruh kelas masalah yang solusinya hampir gratis ketika Anda mulai bekerja dengan rekursi.

Sortir, didefinisikan secara rekursif dalam Python.

def sort( a ):
    if len(a) == 1: return a
    part1= sort( a[:len(a)//2] )
    part2= sort( a[len(a)//2:] )
    return merge( part1, part2 )

Gabungkan, didefinisikan secara rekursif.

def merge( a, b ):
    if len(b) == 0: return a
    if len(a) == 0: return b
    if a[0] < b[0]:
        return [ a[0] ] + merge(a[1:], b)
    else:
        return [ b[0] ] + merge(a, b[1:]) 

Pencarian linier, didefinisikan secara rekursif.

def find( element, sequence ):
    if len(sequence) == 0: return False
    if element == sequence[0]: return True
    return find( element, sequence[1:] )

Pencarian biner, didefinisikan secara rekursif.

def binsearch( element, sequence ):
    if len(sequence) == 0: return False
    mid = len(sequence)//2
    if element < mid: 
        return binsearch( element, sequence[:mid] )
    else:
        return binsearch( element, sequence[mid:] )

Dalam arti tertentu, rekursi adalah tentang pemecahan yang membagi dan menaklukkan, yaitu mengubah ruang masalah menjadi yang lebih kecil untuk membantu menemukan solusi untuk masalah yang sederhana, dan kemudian biasanya kembali merekonstruksi masalah asli untuk menyusun jawaban yang tepat.

Beberapa contoh tidak melibatkan matematika untuk mengajarkan rekursi (setidaknya masalah yang saya ingat dari tahun-tahun universitas saya):

• Menara Hanoi
• Delapan ratu

Ini adalah contoh menggunakan Backtracking untuk menyelesaikan masalah.

Masalah lain adalah klasik dari domain Artificial Intelligence: Menggunakan Depth First Search, pathfinding, planning.

Semua masalah itu melibatkan semacam struktur data "kompleks", tetapi jika Anda tidak ingin mengajarinya dengan matematika (angka) maka pilihan Anda mungkin lebih terbatas. Yoy mungkin ingin mulai mengajar dengan struktur data dasar, seperti Daftar yang ditautkan. Misalnya mewakili bilangan asli menggunakan Daftar:

0 = daftar kosong 1 = daftar dengan satu simpul. 2 = daftar dengan 2 node. ...

kemudian tentukan jumlah dua angka dalam hal struktur data ini seperti ini: Kosong + N = N Node (X) + N = Node (X + N)

Menara Hanoi adalah yang bagus untuk membantu belajar rekursi.

Ada banyak solusi untuk itu di web dalam berbagai bahasa.

Detektor Palindrome:

Mulailah dengan string: "ABCDEEDCBA" Jika karakter awal & akhir sama, maka ulangi dan centang "BCDEEDCB", dll ...

Algoritma pencarian biner terdengar seperti apa yang Anda inginkan.

Dalam bahasa pemrograman fungsional, ketika tidak ada fungsi tingkat tinggi yang tersedia, rekursi digunakan sebagai ganti pengulangan untuk menghindari keadaan yang bisa berubah.

F # adalah bahasa fungsional yang tidak murni yang memungkinkan kedua gaya jadi saya akan membandingkan keduanya di sini. Berikut ini jumlah semua angka dalam daftar.

Imperative Loop dengan Mutable Variable

let xlist = [1;2;3;4;5;6;7;8;9;10]
let mutable sum = 0
for x in xlist do
    sum <- sum + x

Lingkaran Rekursif dengan Tidak Berubah

let xlist = [1;2;3;4;5;6;7;8;9;10]
let rec loop sum xlist = 
    match xlist with
    | [] -> sum
    | x::xlist -> loop (sum + x) xlist
let sum = loop 0 xlist

Perhatikan bahwa agregasi semacam ini ditangkap dalam fungsi tingkat tinggi List.folddan dapat ditulis sebagai List.fold (+) 0 xlistatau bahkan lebih sederhana dengan fungsi kenyamanan List.sumsebagai adil List.sum xlist.

Saya sering menggunakan rekursi dalam bermain game AI. Menulis di C ++, saya menggunakan serangkaian sekitar 7 fungsi yang saling memanggil secara berurutan (dengan fungsi pertama memiliki opsi untuk mem-bypass semua itu dan memanggil rantai 2 fungsi lainnya). Fungsi terakhir dalam rantai mana pun disebut fungsi pertama lagi sampai kedalaman yang ingin saya cari pergi ke 0, dalam hal ini fungsi akhir akan memanggil fungsi evaluasi saya dan mengembalikan skor posisi.

Berbagai fungsi memungkinkan saya untuk dengan mudah melakukan percabangan berdasarkan keputusan pemain atau kejadian acak dalam game. Saya akan menggunakan pass-by-reference kapan pun saya bisa, karena saya sedang membagikan struktur data yang sangat besar, tetapi karena bagaimana game itu disusun, sangat sulit untuk memiliki "undo move" dalam pencarian saya, jadi Saya akan menggunakan pass-by-value dalam beberapa fungsi untuk menjaga data asli saya tidak berubah. Karena itu, beralih ke pendekatan berbasis loop daripada pendekatan rekursif terbukti terlalu sulit.

Anda dapat melihat garis besar yang sangat mendasar dari program semacam ini, lihat https://secure.wikimedia.org/wikipedia/en/wiki/Minimax#Pseudocode

Contoh kehidupan nyata yang sangat baik dalam bisnis adalah sesuatu yang disebut "Bill of Material". Ini adalah data yang mewakili semua komponen yang membentuk produk jadi. Misalnya, mari kita gunakan Sepeda. Sepeda memiliki setang, roda, bingkai, dll. Dan masing-masing komponen dapat memiliki sub-komponen. misalnya Roda dapat memiliki Jari-jari, batang katup, dll. Jadi biasanya ini direpresentasikan dalam struktur pohon.

Sekarang untuk menanyakan informasi agregat tentang BOM atau mengubah elemen dalam BOM sering kali Anda melakukan rekursi.

    class BomPart
    {
        public string PartNumber { get; set; }
        public string Desription { get; set; }
        public int Quantity { get; set; }
        public bool Plastic { get; set; }
        public List<BomPart> Components = new List<BomPart>();
    }

Dan contoh panggilan rekursif ...

    static int ComponentCount(BomPart part)
    {
        int subCount = 0;
        foreach(BomPart p in part.Components)
            subCount += ComponentCount(p);
        return part.Quantity * Math.Max(1,subCount);

    }

Tentunya Kelas BomPart akan memiliki lebih banyak bidang. Anda mungkin perlu mencari tahu berapa banyak komponen plastik yang Anda miliki, berapa banyak tenaga yang diperlukan untuk membangun bagian yang lengkap, dll. Semua ini kembali ke kegunaan Rekursi pada struktur pohon.

Hubungan keluarga menjadi contoh yang baik karena semua orang memahaminya secara intuitif:

ancestor(joe, me) = (joe == me) 
                    OR ancestor(joe, me.father) 
                    OR ancestor(joe, me.mother);

Rekursi yang agak tidak berguna namun menunjukkan bekerja dengan baik adalah rekursif strlen():

size_t strlen( const char* str )
{
    if( *str == 0 ) {
       return 0;
    }
    return 1 + strlen( str + 1 );
}

Tidak ada matematika - fungsi yang sangat sederhana. Tentu saja Anda tidak menerapkannya secara rekursif dalam kehidupan nyata, tetapi ini adalah demo rekursi yang bagus.

Masalah rekursi dunia nyata lain yang mungkin berhubungan dengan siswa adalah membangun perayap web mereka sendiri yang menarik informasi dari situs web dan mengikuti semua tautan di dalam situs itu (dan semua tautan dari tautan itu, dll).

Saya memecahkan masalah dengan pola ksatria (di papan catur) menggunakan program rekursif. Anda seharusnya menggerakkan kesatria itu sehingga menyentuh setiap kotak kecuali beberapa kotak yang ditandai.

Anda hanya:

mark your "Current" square
gather a list of free squares that are valid moves
are there no valid moves?
    are all squares marked?
        you win!
for each free square
    recurse!
clear the mark on your current square.
return.    

Banyak jenis skenario "berpikir-depan" dapat dikerjakan dengan menguji kemungkinan di masa depan dalam pohon seperti ini.