Memahami rekursi [tertutup]

Saya mengalami masalah besar dalam memahami rekursi di sekolah. Setiap kali profesor membicarakannya, saya kelihatannya mengerti tetapi begitu saya mencobanya sendiri, otak saya benar-benar hancur.

Saya mencoba untuk memecahkan Menara Hanoi sepanjang malam dan benar-benar mengejutkan saya. Buku teks saya hanya memiliki sekitar 30 halaman dalam rekursi sehingga tidak terlalu berguna. Adakah yang tahu buku atau sumber yang bisa membantu memperjelas topik ini?

Bagaimana Anda mengosongkan vas berisi lima bunga?

Jawab: jika vas tidak kosong, Anda mengambil satu bunga dan kemudian Anda mengosongkan vas berisi empat bunga.

Bagaimana Anda mengosongkan vas berisi empat bunga?

Jawab: jika vas tidak kosong, Anda mengambil satu bunga dan kemudian Anda mengosongkan vas berisi tiga bunga.

Bagaimana Anda mengosongkan vas berisi tiga bunga?

Jawab: jika vas tidak kosong, Anda mengambil satu bunga dan kemudian Anda mengosongkan vas berisi dua bunga.

Bagaimana Anda mengosongkan vas berisi dua bunga?

Jawab: jika vas tidak kosong, Anda mengambil satu bunga dan kemudian Anda mengosongkan vas yang berisi satu bunga.

Bagaimana Anda mengosongkan vas berisi satu bunga?

Jawab: jika vas tidak kosong, Anda mengambil satu bunga dan kemudian Anda mengosongkan vas yang tidak mengandung bunga.

Bagaimana Anda mengosongkan vas tanpa bunga?

Jawab: jika vas tidak kosong, Anda mengambil satu bunga tetapi vas itu kosong sehingga Anda selesai.

Itu berulang. Mari kita generalisasikan:

Bagaimana Anda mengosongkan vas berisi N bunga?

Jawab: jika vas tidak kosong, Anda mengambil satu bunga dan kemudian Anda mengosongkan vas berisi N-1 bunga.

Hmm, bisakah kita melihatnya dalam kode?

void emptyVase( int flowersInVase ) {
  if( flowersInVase > 0 ) {
   // take one flower and
    emptyVase( flowersInVase - 1 ) ;

  } else {
   // the vase is empty, nothing to do
  }
}

Hmm, tidak bisakah kita melakukan itu dalam for for loop?

Mengapa, ya, rekursi dapat diganti dengan iterasi, tetapi seringkali rekursi lebih elegan.

Mari kita bicara tentang pohon. Dalam ilmu komputer, pohon adalah struktur yang terdiri dari node , di mana setiap node memiliki beberapa anak yang juga node, atau nol. Sebuah pohon biner adalah pohon yang terbuat dari node yang memiliki tepat dua anak, biasanya disebut "kiri" dan "kanan"; lagi-lagi anak-anak bisa menjadi simpul, atau nol. Sebuah akar adalah simpul yang bukan anak dari node lain.

Bayangkan sebuah simpul, di samping anak-anaknya, memiliki nilai, angka, dan bayangkan bahwa kami ingin menjumlahkan semua nilai di beberapa pohon.

Untuk menjumlahkan nilai dalam satu simpul, kami akan menambahkan nilai simpul itu sendiri ke nilai anak kirinya, jika ada, dan nilai anak kanannya, jika ada. Sekarang ingat bahwa anak-anak, jika mereka bukan nol, juga node.

Jadi untuk menjumlahkan anak kiri, kita akan menambahkan nilai simpul anak itu sendiri ke nilai anak kirinya, jika ada, dan nilai anak kanannya, jika ada.

Jadi untuk menjumlahkan nilai anak kiri anak kiri, kita akan menambahkan nilai simpul anak itu sendiri ke nilai anak kirinya, jika ada, dan nilai anak kanannya, jika ada.

Mungkin Anda sudah mengantisipasi ke mana saya akan pergi dengan ini, dan ingin melihat beberapa kode? BAIK:

struct node {
  node* left;
  node* right;
  int value;
} ;

int sumNode( node* root ) {
  // if there is no tree, its sum is zero
  if( root == null ) {
    return 0 ;

  } else { // there is a tree
    return root->value + sumNode( root->left ) + sumNode( root->right ) ;
  }
}

Perhatikan bahwa alih-alih secara eksplisit menguji anak-anak untuk melihat apakah mereka nol atau node, kami hanya membuat fungsi rekursif mengembalikan nol untuk simpul nol.

Jadi katakan kita memiliki pohon yang terlihat seperti ini (angka-angka adalah nilai, garis miring menunjuk ke anak-anak, dan @ berarti pointer menunjuk ke nol):

     5
    / \
   4   3
  /\   /\
 2  1 @  @
/\  /\
@@  @@

Jika kita memanggil sumNode pada root (simpul dengan nilai 5), kita akan kembali:

return root->value + sumNode( root->left ) + sumNode( root->right ) ;
return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ;

Mari kita kembangkan itu di tempatnya. Di mana-mana kita melihat sumNode, kita akan menggantinya dengan perluasan pernyataan kembali:

sumNode( node-with-value-5);
return root->value + sumNode( root->left ) + sumNode( root->right ) ;
return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ;

return 5 + 4 + sumNode( node-with-value-2 ) + sumNode( node-with-value-1 ) 
 + sumNode( node-with-value-3 ) ;  

return 5 + 4 
 + 2 + sumNode(null ) + sumNode( null )
 + sumNode( node-with-value-1 ) 
 + sumNode( node-with-value-3 ) ;  

return 5 + 4 
 + 2 + 0 + 0
 + sumNode( node-with-value-1 ) 
 + sumNode( node-with-value-3 ) ; 

return 5 + 4 
 + 2 + 0 + 0
 + 1 + sumNode(null ) + sumNode( null )
 + sumNode( node-with-value-3 ) ; 

return 5 + 4 
 + 2 + 0 + 0
 + 1 + 0 + 0
 + sumNode( node-with-value-3 ) ; 

return 5 + 4 
 + 2 + 0 + 0
 + 1 + 0 + 0
 + 3 + sumNode(null ) + sumNode( null ) ; 

return 5 + 4 
 + 2 + 0 + 0
 + 1 + 0 + 0
 + 3 + 0 + 0 ;

return 5 + 4 
 + 2 + 0 + 0
 + 1 + 0 + 0
 + 3 ;

return 5 + 4 
 + 2 + 0 + 0
 + 1 
 + 3  ;

return 5 + 4 
 + 2 
 + 1 
 + 3  ;

return 5 + 4 
 + 3
 + 3  ;

return 5 + 7
 + 3  ;

return 5 + 10 ;

return 15 ;

Sekarang lihat bagaimana kita menaklukkan struktur kedalaman dan "percabangan" yang sewenang-wenang, dengan menganggapnya sebagai penerapan berulang template komposit? setiap kali melalui fungsi sumNode kami, kami hanya berurusan dengan satu node, menggunakan cabang if / then tunggal, dan dua pernyataan pengembalian sederhana yang hampir membuat repot, langsung dari spesifikasi kami?

How to sum a node:
 If a node is null 
   its sum is zero
 otherwise 
   its sum is its value 
   plus the sum of its left child node
   plus the sum of its right child node

Itulah kekuatan rekursi.

Contoh vas di atas adalah contoh rekursi ekor . Semua yang dimaksud dengan rekursi ekor adalah bahwa dalam fungsi rekursif, jika kita berulang (yaitu, jika kita memanggil fungsi lagi), itu adalah hal terakhir yang kami lakukan.

Contoh pohon bukanlah rekursif ekor, karena meskipun hal terakhir yang kami lakukan adalah mengembalikan anak yang tepat, sebelum kami melakukannya, kami mengulangi anak kiri.

Bahkan, urutan di mana kami memanggil anak-anak, dan menambahkan nilai node saat ini tidak masalah sama sekali, karena penambahan bersifat komutatif.

Sekarang mari kita lihat operasi di mana pesanan itu penting. Kami akan menggunakan pohon biner node, tetapi kali ini nilai yang dimiliki akan menjadi karakter, bukan angka.

Pohon kami akan memiliki properti khusus, bahwa untuk setiap simpul, karakternya muncul setelah (dalam urutan abjad) karakter yang dipegang oleh anak kirinya dan sebelum (dalam urutan abjad) karakter yang dipegang oleh anak kanannya.

Apa yang ingin kita lakukan adalah mencetak pohon dalam urutan abjad. Itu mudah dilakukan, mengingat properti khusus pohon. Kami hanya mencetak anak kiri, lalu karakter simpul, lalu anak kanan.

Kami tidak hanya ingin mencetak mau tak mau, jadi kami akan melewati fungsi kami sesuatu untuk dicetak. Ini akan menjadi objek dengan fungsi cetak (char); kita tidak perlu khawatir tentang cara kerjanya, hanya ketika cetak dipanggil, itu akan mencetak sesuatu, di suatu tempat.

Mari kita lihat dalam kode:

struct node {
  node* left;
  node* right;
  char value;
} ;

// don't worry about this code
class Printer {
  private ostream& out;
  Printer( ostream& o ) :out(o) {}
  void print( char c ) { out << c; }
}

// worry about this code
int printNode( node* root, Printer& printer ) {
  // if there is no tree, do nothing
  if( root == null ) {
    return ;

  } else { // there is a tree
    printNode( root->left, printer );
    printer.print( value );
    printNode( root->right, printer );
}

Printer printer( std::cout ) ;
node* root = makeTree() ; // this function returns a tree, somehow
printNode( root, printer );

Selain urutan operasi yang sekarang penting, contoh ini menggambarkan bahwa kita dapat meneruskan berbagai hal ke fungsi rekursif. Satu-satunya hal yang harus kita lakukan adalah memastikan bahwa pada setiap panggilan rekursif, kita terus meneruskannya. Kami melewati penunjuk simpul dan printer ke fungsi, dan pada setiap panggilan rekursif, kami melewati mereka "turun".

Sekarang jika pohon kita terlihat seperti ini:

         k
        / \
       h   n
      /\   /\
     a  j @  @
    /\ /\
    @@ i@
       /\
       @@

Apa yang akan kita cetak?

From k, we go left to
  h, where we go left to
    a, where we go left to 
      null, where we do nothing and so
    we return to a, where we print 'a' and then go right to
      null, where we do nothing and so
    we return to a and are done, so
  we return to h, where we print 'h' and then go right to
    j, where we go left to
      i, where we go left to 
        null, where we do nothing and so
      we return to i, where we print 'i' and then go right to
        null, where we do nothing and so
      we return to i and are done, so
    we return to j, where we print 'j' and then go right to
      null, where we do nothing and so
    we return to j and are done, so
  we return to h and are done, so
we return to k, where we print 'k' and then go right to
  n where we go left to 
    null, where we do nothing and so
  we return to n, where we print 'n' and then go right to
    null, where we do nothing and so
  we return to n and are done, so 
we return to k and are done, so we return to the caller

Jadi jika kita hanya melihat garis-garisnya maka kita dicetak:

    we return to a, where we print 'a' and then go right to
  we return to h, where we print 'h' and then go right to
      we return to i, where we print 'i' and then go right to
    we return to j, where we print 'j' and then go right to
we return to k, where we print 'k' and then go right to
  we return to n, where we print 'n' and then go right to

Kita lihat kita mencetak "ahijkn", yang memang dalam urutan abjad.

Kami berhasil mencetak seluruh pohon, dalam urutan abjad, hanya dengan mengetahui cara mencetak satu simpul dalam urutan abjad. Yang mana saja (karena pohon kami memiliki properti khusus nilai pemesanan di sebelah kiri dari nilai yang menurut abjad kemudian) mengetahui untuk mencetak anak kiri sebelum mencetak nilai node, dan untuk mencetak anak yang tepat setelah mencetak nilai node.

Dan itulah kekuatan rekursi: mampu melakukan semua hal dengan mengetahui hanya bagaimana melakukan sebagian dari keseluruhan (dan mengetahui kapan harus berhenti berulang).

Mengingat hal itu di sebagian besar bahasa, operator || ("atau") korsleting ketika operan pertamanya benar, fungsi rekursif umum adalah:

void recurse() { doWeStop() || recurse(); } 

Komentar Luc M:

SO harus membuat lencana untuk jawaban semacam ini. Selamat!

Terima kasih, Luc! Tapi, sebenarnya, karena saya mengedit jawaban ini lebih dari empat kali (untuk menambahkan contoh terakhir, tetapi kebanyakan untuk memperbaiki kesalahan ketik dan memolesnya - mengetik pada keyboard netbook kecil itu sulit), saya tidak bisa mendapatkan poin lagi untuk itu . Yang agak mengecilkan hati saya dari berusaha sebanyak mungkin ke jawaban masa depan.

Lihat komentar saya di sini tentang itu: /programming/128434/what-are-community-wiki-posts-in-stackoverflow/718699#718699

Otak Anda meledak karena mengalami rekursi yang tak terbatas. Itu kesalahan pemula yang umum.

Percaya atau tidak, Anda sudah memahami rekursi, Anda hanya terseret oleh metafora umum, tetapi salah untuk suatu fungsi: kotak kecil dengan barang-barang yang masuk dan keluar.

Pikirkan alih-alih tugas atau prosedur, seperti "cari tahu lebih lanjut tentang rekursi di internet". Itu rekursif dan Anda tidak punya masalah dengan itu. Untuk menyelesaikan tugas ini, Anda mungkin:

a) Baca halaman hasil Google untuk "rekursi"
b) Setelah Anda membacanya, ikuti tautan pertama dan ...
a.1) Baca halaman baru itu tentang rekursi 
b.1) Setelah Anda membacanya, ikuti tautan pertama dan ...
a.2) Baca halaman baru itu tentang rekursi 
b.2) Setelah Anda membacanya, ikuti tautan pertama dan ...

Seperti yang Anda lihat, Anda telah melakukan hal-hal rekursif untuk waktu yang lama tanpa masalah.

Berapa lama Anda akan terus melakukan tugas itu? Selamanya sampai otak Anda meledak? Tentu saja tidak, Anda akan berhenti pada titik tertentu, kapan pun Anda yakin telah menyelesaikan tugas.

Tidak perlu menentukan ini ketika meminta Anda untuk "mencari tahu lebih banyak tentang rekursi di internet", karena Anda adalah manusia dan Anda dapat menyimpulkannya sendiri.

Komputer tidak dapat menyimpulkan jack, jadi Anda harus menyertakan akhir yang eksplisit: "cari tahu lebih lanjut tentang rekursi di internet, SAMPAI Anda memahaminya atau Anda telah membaca maksimal 10 halaman ".

Anda juga menyimpulkan bahwa Anda harus mulai di halaman hasil Google untuk "rekursi", dan sekali lagi itu sesuatu yang tidak bisa dilakukan komputer. Deskripsi lengkap tugas rekursif kami juga harus mencakup titik awal yang eksplisit:

"cari tahu lebih lanjut tentang rekursi di internet, SAMPAI Anda memahaminya atau Anda telah membaca maksimal 10 halaman dan mulai di www.google.com/search?q=recursion "

Untuk memahami semuanya, saya sarankan Anda mencoba salah satu dari buku-buku ini:

• Dasar Umum: Pengantar Lembut untuk Perhitungan Simbolik. Ini adalah penjelasan rekursi non-matematika paling lucu.
• Siasat kecil.

Untuk memahami rekursi, yang harus Anda lakukan adalah melihat label botol sampo Anda:

function repeat()
{
   rinse();
   lather();
   repeat();
}

Masalah dengan ini adalah bahwa tidak ada kondisi terminasi, dan rekursi akan berulang tanpa batas waktu, atau sampai Anda kehabisan sampo atau air panas (kondisi terminasi eksternal, mirip dengan meniup tumpukan Anda).

Jika Anda menginginkan sebuah buku yang bisa menjelaskan tentang rekursi dengan mudah, lihat Gödel, Escher, Bach: An Eternal Golden Braid dari Douglas Hofstadter, khususnya Bab 5. Selain rekursi, buku ini juga menjelaskan pekerjaan yang baik. sejumlah konsep kompleks dalam ilmu komputer dan matematika dengan cara yang dapat dimengerti, dengan satu penjelasan membangun di atas yang lain. Jika Anda belum pernah terpapar konsep-konsep semacam ini sebelumnya, itu bisa menjadi buku yang cukup menggembirakan.

Ini lebih merupakan keluhan daripada pertanyaan. Apakah Anda memiliki pertanyaan lebih spesifik tentang rekursi? Seperti multiplikasi, itu bukan hal yang banyak ditulis orang.

Berbicara tentang multiplikasi, pikirkan ini.

Pertanyaan:

Apa itu * b?

Menjawab:

Jika b adalah 1, itu a. Kalau tidak, itu adalah a + a * (b-1).

Apa itu * (b-1)? Lihat pertanyaan di atas untuk cara menyelesaikannya.

Saya pikir metode yang sangat sederhana ini akan membantu Anda memahami rekursi. Metode ini akan memanggil dirinya sendiri hingga kondisi tertentu benar dan kemudian kembali:

function writeNumbers( aNumber ){
 write(aNumber);
 if( aNumber > 0 ){
  writeNumbers( aNumber - 1 );
 }
 else{
  return;
 }
}

Fungsi ini akan mencetak semua angka dari angka pertama yang Anda beri makan sampai 0. Jadi:

writeNumbers( 10 );
//This wil write: 10 9 8 7 6 5 4 3 2 1 0
//and then stop because aNumber is no longer larger then 0

Apa yang terjadi adalah writeNumber (10) akan menulis 10 dan kemudian memanggil writeNumber (9) yang akan menulis 9 dan kemudian memanggil writeNumber (8) dll. Sampai writeNumber (1) menulis 1 dan kemudian memanggil writeNumber (0) yang akan menulis 0 butt tidak akan memanggil writeNumbers (-1);

Kode ini pada dasarnya sama dengan:

for(i=10; i>0; i--){
 write(i);
}

Lalu mengapa menggunakan rekursi Anda mungkin bertanya, apakah for-loop pada dasarnya sama. Yah Anda kebanyakan menggunakan rekursi ketika Anda harus bersarang untuk loop tetapi tidak akan tahu seberapa dalam mereka bersarang. Misalnya saat mencetak item dari array bersarang:

var nestedArray = Array('Im a string', 
                        Array('Im a string nested in an array', 'me too!'),
                        'Im a string again',
                        Array('More nesting!',
                              Array('nested even more!')
                              ),
                        'Im the last string');
function printArrayItems( stringOrArray ){
 if(typeof stringOrArray === 'Array'){
   for(i=0; i<stringOrArray.length; i++){ 
     printArrayItems( stringOrArray[i] );
   }
 }
 else{
   write( stringOrArray );
 }
}

printArrayItems( stringOrArray );
//this will write:
//'Im a string' 'Im a string nested in an array' 'me too' 'Im a string again'
//'More nesting' 'Nested even more' 'Im the last string'

Fungsi ini bisa mengambil larik yang dapat disarangkan ke dalam 100 level, saat Anda menulis for for loop, Anda harus bersarang sebanyak 100 kali:

for(i=0; i<nestedArray.length; i++){
 if(typeof nestedArray[i] == 'Array'){
  for(a=0; i<nestedArray[i].length; a++){
   if(typeof nestedArray[i][a] == 'Array'){
    for(b=0; b<nestedArray[i][a].length; b++){
     //This would be enough for the nestedAaray we have now, but you would have
     //to nest the for loops even more if you would nest the array another level
     write( nestedArray[i][a][b] );
    }//end for b
   }//endif typeod nestedArray[i][a] == 'Array'
   else{ write( nestedArray[i][a] ); }
  }//end for a
 }//endif typeod nestedArray[i] == 'Array'
 else{ write( nestedArray[i] ); }
}//end for i

Seperti yang Anda lihat metode rekursif jauh lebih baik.

Sebenarnya Anda menggunakan rekursi untuk mengurangi kerumitan masalah yang Anda hadapi. Anda menerapkan rekursi sampai Anda mencapai kasus dasar sederhana yang dapat diselesaikan dengan mudah. Dengan ini, Anda dapat memecahkan langkah rekursif terakhir. Dan dengan ini semua langkah rekursif lainnya hingga masalah awal Anda.

Saya akan mencoba menjelaskannya dengan sebuah contoh.

Anda tahu apa n! cara? Jika tidak: http://en.wikipedia.org/wiki/Factorial

3! = 1 * 2 * 3 = 6

ini dia beberapa pseudocode

function factorial(n) {
  if (n==0) return 1
  else return (n * factorial(n-1))
}

Jadi mari kita coba:

factorial(3)

Apakah n 0?

tidak!

jadi kami menggali lebih dalam dengan rekursi kami:

3 * factorial(3-1)

3-1 = 2

adalah 2 == 0?

tidak!

jadi kita masuk lebih dalam! 3 * 2 * faktorial (2-1) 2-1 = 1

Apakah 1 == 0?

tidak!

jadi kita masuk lebih dalam! 3 * 2 * 1 * faktorial (1-1) 1-1 = 0

adalah 0 == 0?

Iya!

kami punya kasus sepele

jadi kita punya 3 * 2 * 1 * 1 = 6

semoga yang membantu kamu

Pengulangan

Metode A, memanggil Metode A memanggil Metode A. Akhirnya salah satu dari metode ini A tidak akan memanggil dan keluar, tetapi rekursi karena sesuatu memanggil dirinya sendiri.

Contoh rekursi di mana saya ingin mencetak setiap nama folder pada hard drive: (dalam c #)

public void PrintFolderNames(DirectoryInfo directory)
{
    Console.WriteLine(directory.Name);

    DirectoryInfo[] children = directory.GetDirectories();

    foreach(var child in children)
    {
        PrintFolderNames(child); // See we call ourself here...
    }
}

Buku mana yang Anda gunakan?

Buku teks standar tentang algoritma yang benar-benar bagus adalah Cormen & Rivest. Pengalaman saya adalah bahwa ia mengajarkan rekursi dengan cukup baik.

Rekursi adalah salah satu bagian sulit pemrograman untuk dipahami, dan meski memang membutuhkan naluri, ia bisa dipelajari. Tetapi memang perlu deskripsi yang baik, contoh yang baik, dan ilustrasi yang baik.

Juga, 30 halaman pada umumnya banyak, 30 halaman dalam satu bahasa pemrograman membingungkan. Jangan mencoba mempelajari rekursi dalam bahasa C atau Java, sebelum Anda memahami rekursi secara umum dari buku umum.

Fungsi rekursif hanyalah fungsi yang memanggil dirinya sendiri sebanyak yang diperlukan. Ini berguna jika Anda perlu memproses sesuatu beberapa kali, tetapi Anda tidak yakin berapa kali sebenarnya diperlukan. Di satu sisi, Anda bisa memikirkan fungsi rekursif sebagai jenis loop. Akan tetapi, seperti sebuah loop, Anda harus menentukan kondisi untuk proses yang akan rusak jika tidak maka akan menjadi tak terbatas.

http://javabat.com adalah tempat yang menyenangkan dan menyenangkan untuk berlatih rekursi. Contoh-contoh mereka mulai cukup ringan dan bekerja melalui ekstensif (jika Anda ingin mengambil sejauh itu). Catatan: Pendekatan mereka adalah belajar dengan berlatih. Berikut ini adalah fungsi rekursif yang saya tulis untuk hanya mengganti loop for.

Untuk loop:

public printBar(length)
{
  String holder = "";
  for (int index = 0; i < length; i++)
  {
    holder += "*"
  }
  return holder;
}

Inilah rekursi untuk melakukan hal yang sama. (perhatikan kami membebani metode pertama untuk memastikan itu digunakan seperti di atas). Kami juga memiliki metode lain untuk mempertahankan indeks kami (mirip dengan cara pernyataan for melakukannya untuk Anda di atas). Fungsi rekursif harus mempertahankan indeks mereka sendiri.

public String printBar(int Length) // Method, to call the recursive function
{
  printBar(length, 0);
}

public String printBar(int length, int index) //Overloaded recursive method
{
  // To get a better idea of how this works without a for loop
  // you can also replace this if/else with the for loop and
  // operationally, it should do the same thing.
  if (index >= length)
    return "";
  else
    return "*" + printBar(length, index + 1); // Make recursive call
}

Singkatnya, rekursi adalah cara yang baik untuk menulis lebih sedikit kode. Dalam pemberitahuan printBar yang terakhir bahwa kita memiliki pernyataan if. JIKA kondisi kita telah tercapai, kita akan keluar dari rekursi dan kembali ke metode sebelumnya, yang kembali ke metode sebelumnya, dll. Jika saya mengirim printBar (8), saya mendapatkan ********. Saya berharap bahwa dengan contoh fungsi sederhana yang melakukan hal yang sama seperti untuk loop yang mungkin ini akan membantu. Anda dapat berlatih ini lebih banyak di Java Bat.

Cara yang benar-benar matematis untuk melihat membangun fungsi rekursif adalah sebagai berikut:

1: Bayangkan Anda memiliki fungsi yang benar untuk f (n-1), bangun f sedemikian rupa sehingga f (n) benar. 2: Bangun f, sehingga f (1) benar.

Ini adalah bagaimana Anda dapat membuktikan bahwa fungsinya benar, secara matematis, dan itu disebut Induksi . Ini sama dengan memiliki kasus dasar yang berbeda, atau fungsi yang lebih rumit pada banyak variabel). Ini juga sama dengan membayangkan bahwa f (x) benar untuk semua x

Sekarang untuk contoh "sederhana". Bangun fungsi yang dapat menentukan apakah mungkin untuk memiliki kombinasi koin 5 sen dan 7 sen untuk menghasilkan x sen. Misalnya, dimungkinkan memiliki 17 sen 2x5 + 1x7, tetapi tidak mungkin memiliki 16 sen.

Sekarang bayangkan Anda memiliki fungsi yang memberi tahu Anda apakah mungkin membuat x sen, selama x <n. Panggil fungsi ini can_create_coins_small. Seharusnya cukup sederhana untuk membayangkan bagaimana membuat fungsi untuk n. Sekarang bangun fungsi Anda:

bool can_create_coins(int n)
{
    if (n >= 7 && can_create_coins_small(n-7))
        return true;
    else if (n >= 5 && can_create_coins_small(n-5))
        return true;
    else
        return false;
}

Kuncinya di sini adalah untuk menyadari bahwa fakta bahwa can_create_coins berfungsi untuk n, berarti Anda dapat mengganti can_create_coins dengan can_create_coins_small, dengan memberikan:

bool can_create_coins(int n)
{
    if (n >= 7 && can_create_coins(n-7))
        return true;
    else if (n >= 5 && can_create_coins(n-5))
        return true;
    else
        return false;
}

Satu hal terakhir yang harus dilakukan adalah memiliki kasus dasar untuk menghentikan rekursi tak terbatas. Perhatikan bahwa jika Anda mencoba membuat 0 sen, maka itu dimungkinkan dengan tidak memiliki koin. Menambahkan kondisi ini memberi:

bool can_create_coins(int n)
{
    if (n == 0)
        return true;
    else if (n >= 7 && can_create_coins(n-7))
        return true;
    else if (n >= 5 && can_create_coins(n-5))
        return true;
    else
        return false;
}

Dapat dibuktikan bahwa fungsi ini akan selalu kembali, menggunakan metode yang disebut infinite descent , tetapi itu tidak perlu di sini. Anda dapat membayangkan bahwa f (n) hanya memanggil nilai n yang lebih rendah, dan pada akhirnya akan selalu mencapai 0.

Untuk menggunakan informasi ini untuk menyelesaikan masalah Tower of Hanoi Anda, saya pikir triknya adalah dengan menganggap Anda memiliki fungsi untuk memindahkan tablet n-1 dari a ke b (untuk a / b), mencoba memindahkan n tabel dari a ke b .

Contoh rekursif sederhana dalam Common Lisp :

MYMAP menerapkan fungsi ke setiap elemen dalam daftar.

1) daftar kosong tidak memiliki elemen, jadi kami mengembalikan daftar kosong - () dan NIL keduanya adalah daftar kosong.

2) menerapkan fungsi ke daftar pertama, panggil MYMAP untuk sisa daftar (panggilan rekursif) dan gabungkan kedua hasil ke dalam daftar baru.

(DEFUN MYMAP (FUNCTION LIST)
  (IF (NULL LIST)
      ()
      (CONS (FUNCALL FUNCTION (FIRST LIST))
            (MYMAP FUNCTION (REST LIST)))))

Mari kita lihat eksekusi yang dilacak. Pada MASUKKAN fungsi, argumen dicetak. Pada EXITing function, hasilnya dicetak. Untuk setiap panggilan rekursif, output akan diindentasi pada level.

Contoh ini memanggil fungsi SIN pada setiap nomor dalam daftar (1 2 3 4).

Command: (mymap 'sin '(1 2 3 4))

1 Enter MYMAP SIN (1 2 3 4)
| 2 Enter MYMAP SIN (2 3 4)
|   3 Enter MYMAP SIN (3 4)
|   | 4 Enter MYMAP SIN (4)
|   |   5 Enter MYMAP SIN NIL
|   |   5 Exit MYMAP NIL
|   | 4 Exit MYMAP (-0.75680256)
|   3 Exit MYMAP (0.14112002 -0.75680256)
| 2 Exit MYMAP (0.9092975 0.14112002 -0.75680256)
1 Exit MYMAP (0.841471 0.9092975 0.14112002 -0.75680256)

Ini adalah hasil kami :

(0.841471 0.9092975 0.14112002 -0.75680256)

Untuk menjelaskan rekursi ke anak enam tahun, pertama jelaskan ke anak lima tahun, lalu tunggu satu tahun.

Sebenarnya, ini adalah contoh balasan yang berguna, karena panggilan rekursif Anda harus lebih sederhana, bukan lebih keras. Akan lebih sulit untuk menjelaskan rekursi kepada anak berusia lima tahun, dan meskipun Anda dapat menghentikan rekursi pada angka 0, Anda tidak memiliki solusi sederhana untuk menjelaskan rekursi kepada anak berusia nol tahun.

Untuk memecahkan masalah menggunakan rekursi, pertama-tama bagilah menjadi satu atau lebih masalah sederhana yang dapat Anda selesaikan dengan cara yang sama, dan kemudian ketika masalahnya cukup sederhana untuk diselesaikan tanpa rekursi lebih lanjut, Anda dapat kembali ke tingkat yang lebih tinggi.

Bahkan, itu adalah definisi rekursif tentang bagaimana menyelesaikan masalah dengan rekursi.

Anak-anak secara implisit menggunakan rekursi, misalnya:

Perjalanan ke Disney World

Apakah kita sudah sampai?

Apakah kita sudah sampai?

Apakah kita sudah sampai? (Hampir ...)

Apakah kita sudah sampai? (SHHHH)

Apakah kita sudah sampai?(!!!!!)

Pada saat anak itu tertidur ...

Fungsi hitung mundur ini adalah contoh sederhana:

function countdown()
      {
      return (arguments[0] > 0 ?
        (
        console.log(arguments[0]),countdown(arguments[0] - 1)) : 
        "done"
        );
      }
countdown(10);

Hukum Hofstadter yang diterapkan pada proyek perangkat lunak juga relevan.

Esensi bahasa manusia adalah, menurut Chomsky, kemampuan otak yang terbatas untuk menghasilkan apa yang ia anggap sebagai tata bahasa yang tak terbatas. Maksudnya bukan hanya tidak ada batas atas pada apa yang bisa kita katakan, tetapi juga tidak ada batas atas jumlah kalimat yang dimiliki bahasa kita, tidak ada batas atas pada ukuran kalimat tertentu. Chomsky telah mengklaim bahwa alat dasar yang mendasari semua kreativitas bahasa manusia ini adalah rekursi: kemampuan bagi satu frasa untuk terulang kembali di dalam frasa lain dari jenis yang sama. Jika saya mengatakan "rumah saudara Yohanes", saya memiliki kata benda, "rumah", yang muncul dalam frasa kata benda, "rumah saudara", dan frasa kata benda itu muncul dalam frasa kata benda lain, "rumah saudara laki-laki John". Ini sangat masuk akal, dan itu

Referensi

• Rekursi dan Pemikiran Manusia

Ketika bekerja dengan solusi rekursif, saya selalu berusaha untuk:

• Tetapkan kasus dasar pertama yaitu ketika n = 1 dalam solusi faktorial
• Cobalah untuk membuat aturan umum untuk setiap kasus lainnya

Juga ada berbagai jenis solusi rekursif, ada pendekatan membagi dan menaklukkan yang berguna untuk fraktal dan banyak lainnya.

Ini juga akan membantu jika Anda dapat mengerjakan masalah yang lebih sederhana terlebih dahulu hanya untuk menguasainya. Beberapa contoh memecahkan untuk faktorial dan menghasilkan angka fibonacci ke-n.

Untuk referensi, saya sangat merekomendasikan Algoritma oleh Robert Sedgewick.

Semoga itu bisa membantu. Semoga berhasil.

Aduh. Saya mencoba mencari tahu Menara Hanoi tahun lalu. Hal rumit tentang TOH adalah ini bukan contoh rekursi yang sederhana - Anda memiliki rekursi bersarang yang juga mengubah peran menara pada setiap panggilan. Satu-satunya cara saya bisa membuatnya masuk akal adalah dengan secara visual memvisualisasikan pergerakan cincin di mata pikiran saya, dan mengucapkan apa panggilan rekursif itu nantinya. Saya akan mulai dengan satu dering, kemudian dua, kemudian tiga. Saya sebenarnya memesan game di internet. Butuh waktu sekitar dua atau tiga hari bagi otak saya untuk mendapatkannya.

Fungsi rekursif seperti pegas yang Anda kompres sedikit pada setiap panggilan. Pada setiap langkah, Anda menaruh sedikit informasi (konteks saat ini) pada tumpukan. Ketika langkah terakhir tercapai, pegas dilepaskan, mengumpulkan semua nilai (konteks) sekaligus!

Tidak yakin metafora ini efektif ... :-)

Lagi pula, di luar contoh klasik (faktorial yang merupakan contoh terburuk karena tidak efisien dan mudah diratakan, Fibonacci, Hanoi ...) yang agak artifisial (saya jarang, jika pernah, menggunakannya dalam kasus pemrograman nyata), itu adalah menarik untuk melihat di mana itu benar-benar digunakan.

Kasus yang sangat umum adalah berjalan di pohon (atau grafik, tetapi pohon lebih umum, secara umum).
Misalnya, hierarki folder: untuk membuat daftar file, Anda mengulanginya. Jika Anda menemukan sub-direktori, fungsi yang mencantumkan file memanggil dirinya sendiri dengan folder baru sebagai argumen. Ketika kembali dari daftar folder baru ini (dan sub-foldernya!), Ia melanjutkan konteksnya, ke file berikutnya (atau folder).
Kasus konkret lainnya adalah ketika menggambar hierarki komponen GUI: biasanya memiliki wadah, seperti panel, untuk memegang komponen yang dapat berupa panel juga, atau komponen majemuk, dll. Rutinitas pengecatan memanggil secara rekursif fungsi cat dari masing-masing komponen, yang memanggil fungsi cat dari semua komponen yang dipegangnya, dll.

Tidak yakin apakah saya sangat jelas, tetapi saya ingin menunjukkan penggunaan materi pengajaran di dunia nyata, karena itu adalah sesuatu yang saya temukan di masa lalu.

Pikirkan lebah pekerja. Mencoba membuat madu. Ia melakukan tugasnya dan mengharapkan lebah pekerja lainnya mengambil sisa madu. Dan ketika sarang madu penuh, itu berhenti.

Pikirkan itu sebagai sihir. Anda memiliki fungsi yang memiliki nama yang sama dengan yang Anda coba terapkan dan ketika Anda memberikan subproblem, itu memecahkannya untuk Anda dan satu-satunya hal yang perlu Anda lakukan adalah mengintegrasikan solusi bagian Anda dengan solusi itu. memberimu.

Misalnya, kami ingin menghitung panjang daftar. Mari kita panggil fungsi kita magical_length dan penolong magis kita dengan magical_length Kita tahu bahwa jika kita memberikan sublist yang tidak memiliki elemen pertama, itu akan memberi kita panjang sublist dengan sihir. Maka satu-satunya hal yang perlu kita pikirkan adalah bagaimana mengintegrasikan informasi ini dengan pekerjaan kita. Panjang elemen pertama adalah 1 dan magic_counter memberi kita panjang sublist n-1, oleh karena itu total panjangnya adalah (n-1) + 1 -> n

int magical_length( list )
  sublist = rest_of_the_list( list )
  sublist_length = magical_length( sublist ) // you can think this function as magical and given to you
  return 1 + sublist_length

Namun jawaban ini tidak lengkap karena kami tidak mempertimbangkan apa yang terjadi jika kami memberikan daftar kosong. Kami berpikir bahwa daftar kami selalu memiliki setidaknya satu elemen. Karena itu kita perlu memikirkan apa yang seharusnya menjadi jawaban jika kita diberikan daftar kosong dan jawabannya jelas 0. Jadi tambahkan informasi ini ke fungsi kita dan ini disebut kondisi base / edge.

int magical_length( list )
  if ( list is empty) then
    return 0
  else
    sublist_length = magical_length( sublist ) // you can think this function as magical and given to you
    return 1 + sublist_length