Rekursi — Cara Kerja, Contoh & Kasus Dasar

Rekursi dalam matematika berarti mendefinisikan fungsi, barisan, atau proses dengan menggunakan kasus-kasus yang lebih kecil dari gagasan yang sama. Definisi rekursif hanya bekerja jika memuat kasus dasar dan aturan yang mengarahkan setiap kasus baru menuju kasus dasar tersebut.

Jika Anda hanya membutuhkan gagasan intinya, inilah poin utamanya: rekursi berhenti berguna saat aturan langkah-kecilnya tidak lagi mencapai titik berhenti yang valid.

Apa arti rekursi dalam matematika

Definisi rekursif tidak mencantumkan setiap kasus secara terpisah. Sebaliknya, definisi ini memberikan titik awal dan aturan untuk membangun kasus yang lebih besar dari kasus yang lebih kecil.

Ini berbeda dari rumus langsung. Rumus langsung memberikan jawaban dari input dalam satu ekspresi. Definisi rekursif mengurangi masalah selangkah demi selangkah sampai mencapai kasus yang sudah diketahui.

Mengapa kasus dasar diperlukan

Kasus dasar adalah titik berhenti. Tanpanya, definisi akan terus merujuk ke kasus yang semakin kecil tanpa pernah selesai.

Kasus dasar juga harus sesuai dengan aturan yang Anda pilih. Jika langkah rekursif mengurangi dari $n$ ke $n-1$, maka kasus dasar harus dapat dicapai dari pola itu untuk input yang Anda izinkan.

Contoh lengkap: rekursi faktorial

Faktorial adalah definisi rekursif yang standar. Untuk bilangan bulat tak negatif $n \ge 0$, definisikan faktorial dengan

$$0! = 1$$

dan, untuk $n \ge 1$,

$$n! = n(n-1)!$$

Di sini, $0! = 1$ adalah kasus dasar, dan $n! = n(n-1)!$ adalah langkah rekursif.

Untuk mencari $4!$, terus sederhanakan sampai kasus dasar muncul:

$$4! = 4 \cdot 3! = 4 \cdot 3 \cdot 2! = 4 \cdot 3 \cdot 2 \cdot 1! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 0!$$

Sekarang terapkan kasus dasar $0! = 1$:

$$4! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 1 = 24$$

Inilah pola rekursi secara lengkap: reduksi ke kasus yang lebih kecil, capai kasus dasar, lalu hitung kembali ke pertanyaan semula.

Rekursi vs. relasi rekurensi

Rekursi adalah gagasan yang lebih luas. Relasi rekurensi adalah aturan rekursif untuk suatu barisan, ketika setiap suku bergantung pada suku-suku sebelumnya.

Sebagai contoh, barisan Fibonacci diberikan oleh relasi rekurensi karena setiap suku didefinisikan dari suku-suku sebelumnya. Faktorial juga bersifat rekursif, tetapi biasanya disajikan sebagai definisi rekursif dari suatu fungsi, bukan sebagai rekurensi untuk sebuah barisan.

Kesalahan umum dalam rekursi

Tidak menyertakan kasus dasar

Jika tidak ada kasus dasar, definisi tidak akan selesai.

Menggunakan langkah yang tidak mengecil

Jika langkah rekursif tidak bergerak menuju kasus dasar, prosesnya bisa berulang tanpa akhir atau menjadi tidak terdefinisi untuk beberapa input.

Melupakan syarat pada aturan

Dalam contoh faktorial, aturan $n! = n(n-1)!$ digunakan untuk $n \ge 1$. Syarat itu penting. Tanpanya, Anda bisa mencoba menerapkan aturan pada tempat yang memang tidak dimaksudkan oleh definisi.

Menganggap rekursi hanya gagasan dalam pemrograman

Rekursi muncul dalam matematika jauh sebelum kode. Rekursi adalah cara mendefinisikan fungsi, barisan, dan himpunan dengan merujuk pada kasus-kasus yang lebih kecil. Induksi kemudian sering digunakan untuk membuktikan pernyataan tentang definisi-definisi rekursif tersebut.

Kapan rekursi berguna

Rekursi berguna ketika suatu masalah secara alami dapat dipecah menjadi versi-versi yang lebih kecil dari dirinya sendiri. Anda dapat melihatnya pada faktorial, barisan tipe Fibonacci, himpunan yang didefinisikan secara rekursif, dan banyak algoritma.

Rekursi sangat membantu ketika kasus yang lebih kecil memiliki struktur yang sama dengan kasus aslinya. Jika kasus yang lebih kecil sebenarnya bukan jenis masalah yang sama, rekursi biasanya bukan alat yang tepat.

Uji cepat untuk definisi rekursif yang baik

Ajukan dua pertanyaan:

1. Apakah saya punya kasus dasar?
2. Apakah setiap langkah rekursif bergerak lebih dekat ke sana?

Jika salah satu jawabannya tidak, definisinya perlu diperbaiki.

Coba soal serupa

Definisikan suatu barisan dengan

$$a_1 = 2, \qquad a_n = a_{n-1} + 3 \quad \text{for } n \ge 2$$

Lalu tentukan $a_2$, $a_3$, dan $a_4$. Ini adalah cara cepat untuk berlatih mengenali kasus dasar dan langkah rekursif dalam situasi yang baru.