Recursion

Recursion merupakan salah satu metode pemecahan masalah dimana sebuah solusi pada masalah tersebut bergantung pada solusi dari masalah yang lebih kecil yang merupakan bagian dari masalah tersebut. Recursion adalah salah satu hal yang paling penting di bidang Computer Science dan sebaiknya dikuasai oleh mereka yang bergelut di bidangtersebut.

Bahasa pemrograman biasanya mengimplementasikan recursion ini dengan mengijinkan sebuah fungsi untuk memanggil dirinya sendiri. Pada pembentukan fungsi dengan recursion atau lebih dikenal dengan recursive function,terdapat dua hal yang penting, yakni penentuan: base case dan step reduction.

Secara umum, base case merupakan kondisi dimana fungsi akan berhenti (tidak lagi berulang) dan step reduction adalah bagaimana agar fungsi tersebut kembali memanggil dirinya sendiri dengan tahapan hingga mencapai base case.

Sebagai contoh, pada operasi perhitungan factorial, dimana kita ketahui bahwa factorial merupakan hasil yang didapatkan dengan mengalikan angka yang ada hingga mencapai nilai 1.
Contoh: Faktorial dari 5 adalah 5 * 4 * 3 * 2 * 1 = 120.

Dengan demikian kita ketahui bahwa:

5! = 5 * 4 * 3 * 2 * 1
4! = 4 * 3 * 2 * 1
3! = 3 * 2 * 1
1! = 1
0! = 1

Secara tidak langsung artinya:

5! = 5 * 4!
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1
0! = 1

Bila kita definisikan dalam bentuk recursive function, maka kita dapatkan bahwa bila nilai akan berhenti pada saat bertemu 0 atau 1. Hal inilah yang disebut dengan base case.

Sedangkan dapat kita lihat bahwa hasil factorial kita dapatkan dengan mereduksi nilai sebanyak 1 (contoh 5! Adalah 5 * 4! =>dari 5 ke 4).

Dengan demikian, step reductionnya adalah:

N! = N * (N-1)!

Atau bila kita terjemahkan: factorial(N) = N * factorial (N-1).

Fungsi factorial yang dibahas ini dapat didefinisikan sebagai berikut:

Pada program di atas bila: factorial(5) dipanggil akan menghasilkan instruksi sebagai berikut:

Sehingga di dapatkan bahwa factorial 5 adalah 5 * 4 * 3 * 2 * 1 = 120.