Rekursif

Rekursif merupakan suatu teknik pemograman yang mengizinkan seorang pemogram untuk menggunakan istilah dalam menyatakan operasi dalam kaitan dengan dirinya sendiri.

Di dalam C++, rekursif mengambil bentuk suatu fungsi yang memanggil diri sendiri dengan memasukkan suatu nilai yang lebih sederhana dan memperoleh hasil dengan masukkan yang sederhana dengan menerapkan operasi yang sederhana untuk mengembalikan nilai masukkan yang lebih sederhana.

Salah satu konsep paling dasar dalam ilmu komputer dan pemrograman adalah pengunaan fungsi sebagai abstraksi untuk kode-kode yang digunakan berulang kali. Kedekatan ilmu komputer dengan matematika juga menyebabkan konsep-konsep fungsi pada matematika seringkali dijumpai. Salah satu konsep fungsi pada matematika yang ditemui pada ilmu komputer adalah fungsi rekursif: sebuah fungsi yang memanggil dirinya sendiri.

Kode berikut memperlihatkan contoh fungsi rekursif, untuk menghitung hasil kali dari dua bilangan:

def kali(a, b):
    return a if b == 1 else a + kali(a, b - 1)

Bagaimana cara kerja fungsi rekursif ini? Sederhananya, selama nilai b bukan 1, fungsi akan terus memanggil perintaha + kali(a, b - 1), yang tiap tahapnya memanggil dirinya sendiri sambil mengurangi nilai b. Mari kita coba panggil fungsi kali dan uraikan langkah pemanggilannya:

kali(2, 4)
  -> 2 + kali(2, 3)
  -> 2 + (2 + kali(2, 2))
  -> 2 + (2 + (2 + kali(2, 1)))
  -> 2 + (2 + (2 + 2))
  -> 2 + (2 + 4)
  -> 2 + 6
  -> 8

Perhatikan bahwa sebelum melakukan penambahan program melakukan pemanggilan fungsi rekursif terlebih dahulu sampai fungsi rekursif mengembalikan nilai pasti (2). Setelah menghilangkan semua pemanggilan fungsi, penambahan baru dilakukan, mulai dari nilai kembalian dari fungsi yang paling terakhir. Mari kita lihat contoh fungsi rekursif lainnya, yang digunakan untuk melakukan perhitungan faktorial:

def faktorial(n):
    return n if n == 1 else n * faktorial(n - 1)

Fungsi faktorial memiliki cara kerja yang sama dengan fungsi kali. Mari kita panggil dan lihat langkah pemanggilannya:

faktorial(5)
  -> 5 * faktorial(4)
  -> 5 * (4 * faktorial(3))
  -> 5 * (4 * (3 * faktorial(2)))
  -> 5 * (4 * (3 * (2 * faktorial(1))))
  -> 5 * (4 * (3 * (2 * 1)))
  -> 5 * (4 * (3 * 2))
  -> 5 * (4 * 6)
  -> 5 * 24
  -> 120

Dengan melihat kemiripan cara kerja serta kode dari fungsi faktorial dan kali, kita dapat melihat bagaimana fungsi rekursif memiliki dua ciri khas:

1. Fungsi rekursif selalu memiliki kondisi yang menyatakan kapan fungsi tersebut berhenti. Kondisi ini harus dapat dibuktikan akan tercapai, karena jika tidak tercapai maka kita tidak dapat membuktikan bahwa fungsi akan berhenti, yang berarti algoritma kita tidak benar.
2. Fungsi rekursif selalu memanggil dirinya sendiri sambil mengurangi atau memecahkan data masukan setiap panggilannya. Hal ini penting diingat, karena tujuan utama dari rekursif ialah memecahkan masalah dengan mengurangi masalah tersebut menjadi masalah-masalah kecil.

Setiap fungsi rekursif yang ada harus memenuhi kedua persyaratan di atas untuk memastikan fungsi rekursif dapat berhenti dan memberikan hasil. Kebenaran dari nilai yang dihasilkan tentu saja memerlukan pembuktian dengan cara tersendiri. Tetapi sebelum masuk ke analisa dan pembuktian fungsi rekursif, mari kita lihat kegunaan dan contoh-contoh fungsi rekursif lainnya lagi.

Pada beberapa persoalan, fungsi rekursif sangat berguna karena mempermudah solusi. Namun demikian, fungsi rekursif juga memiliki kelemahan, yakni memungkinkan tejadinya overflow pada stack, yang berarti stack tidak lagi mampu menangani permintaan pemanggilan fungsi karena kehabisan memori stack. Memori stack adalah suatu area memori yang dipakai untuk variable lokal untuk mengalokasikan suatu memori ketika suatu fungsi dipanggil. 

Berikut bentuk umum dari fungsi rekursif :

              Nama_fungsi(parameter_list)

              {

                   ...

                   Nama_fungsi(parameter_list);

                   ...

               }

Contoh sederhana dari fungsi rekursif :

               void recurse()

               {

                     recurse(): /* Pemanggilan fungsi dirinya sendiri */

               }

               int mai()

               {

                     recurse(): /* Set pengulangan */

                     return 0;

               }

Cara terbaik untuk berpikir tentang rekursif adalah bahwa setiap panggilan fungsi adalah satu proses yang dilaksanakan oleh komputer. Jika kita berpikir tentang suatu program yang dilaksanakan oleh suatu kelompok orang yang dapat memberikan informasi tentang status dari suatu task dan instruksi pada hasil task, yang dimana stiap panggilan fungsi yang berulang merupakan permintaan berikutnya untuk mengikuti set instruksi yang sama di beberapa bagian dari task selagi orang pertama menunggu hasil.

Pada saat tertentu, kita akan kehabisan orang-orang untuk menyelesaikan instruksi, sama seperti fungsi-fungsi rekursif yang kehabisan ruang di tumpukkan. Dimana perlu adanya suatu cara untuk menghindari hal ini. Untuk menghentikan satu rangkaian panggilan rekursif, suatu fungsi akan memiliki suatu kondisi yang mengendalikan kapan fungsi itu akan berkahir memanggil diri sendiri. Kondisi ini sebagai kasus dasar dari fungsi. Maksudnya ialah jika statemet memeriksa beberapa variabel untuk suatu kondisi (yang kurang dari nol atau lebih besar) dan jika kondisi itu adala benar, maka tidak akan diizinkan fungsi untuk memanggil diri sendiri lagi.

Contoh sederhana dari fungsi rekursif yang dibatasi oleh kasus tertentu :

           void count_to_ten (int count)

           {

                     if (count < 10)

                    {

                          count_to_ten (count +1);

                    }

            }

Tujuan program ini menghentikan hitungan ketika hitungan sudah tidak lagi kurang dari sepuluh. Ini adalah suatu hal yang baik karena ini berarti jika kita mempunyai satu masukan lebih besar dari sepuluh, kita akan berhenti dengan segera. Jika kita memilih untuk berhenti ketika hitungan sampai dengan sepuluh, lalu jika fungsi itu memanggil masukan ke-11, hal itu akan sebagai isyarat ke memori sebelum berhenti.

Bagaimana bila satu fungsi bisa mencetak angka-angka 123456789987654321 menggunakan pengulangan untuk menulis suatu fungsi untuk lakukan hal ini? Solusi sederhan adalah dengan menjaga kenaikan suatu variabel yang dilewatkan, kemudian menjadi variabel keluaran yang berikutnya: yakni satu kali sebelum fungsi rekursif dan ketika setelah fungsi rekursif.

              void printum (int begin)

              {

                     printf("%d", begin);

                     if (begin < 9)

                     {

                           printnum (begin + 1);

                      }

                      printf("%d", begin);

               }

Fungsi ini bekerja karena fungsi akan mengalami dan mencetak angka-angka mulai 1 sampai 9, kemudian setiap fungsi printnum berkahir akan dilanjutkan dengan pencetakkan nilai mulai dari 9 sampai 1.