Rekursi dalam Pemrograman Komputer

Rekursi merupakan teknik pemrograman yang menyebabkan suatu fungsi/prosedur memanggil dirinya sendiri. Pemanggilan diri sendiri ini berlangsung terus menerus sampai batas terkecil yang nilai dari fungsi tersebut disebutkan secara eksplisit. Salah satu contoh dari penerapan rekursi adalah perhitungan faktorial. Dalam faktorial, n! = n*(n-1)! dengan pengecualian 0! = 1. Berikut contoh perhitungannya:

0! = 1
1! = 1          = 1*(0!) = 1
2! = 2*1       = 2*(1!) = 2
3! = 3*2*1    = 3*(2!) = 6
4! = 4*3*2*1 = 4*(3!) = 24
dan seterusnya...

Dengan menggunakan pendekatan bahasa pemrograman, contoh perhitungan diatas dapat juga ditulis seperti berikut ini:

faktorial(0) = 1
faktorial(1) = 1 * faktorial(0)
faktorial(2) = 2 * faktorial(1)
faktorial(3) = 3 * faktorial(2)
faktorial(4) = 4 * faktorial(3)

Atau lebih singkatnya yaitu:

if (n == 0)
  faktorial(n) = 1;
else
  faktorial(n) = n * faktorial(n-1);

Sampai disini sudah mulai terlihat jelas wujud dari penerapan rekursi. Fungsi faktorial(n) diatas adalah contoh dari rekursi. Berikut ini contoh program lengkap yang menerapkan rekursi dalam perhitungan faktorial:

using System;

namespace Rekursi
{
  class Aritmatika
  {
    public static void Main(string[] args)
    {
      Console.Clear();
      Console.WriteLine("Menghitung faktorial n \n");
      Console.Write("n = ");
      int n = Int32.Parse(Console.ReadLine());
            
      Aritmatika hitung = new Aritmatika();   
      Console.WriteLine("{0}! = {1} ",n,hitung.faktorial(n));    
    }
  
    // fungsi rekursi
    long faktorial(int n)
    {
      try
      {
        if (n == 0) 
          return (1);
        else 
          return (n * faktorial(n-1));
      }
            
      catch (Exception e)
      {
        Console.WriteLine(e.ToString());
        return 1;
      }
    } 
  }
}

Urutan proses pemanggilan fungsi faktorial diatas adalah sebagai berikut (sebagai contoh misal n=4):
1. faktorial(4) = 4 * faktorial(3)
2. faktorial(3) = 3 * faktorial(2)
3. faktorial(2) = 2 * faktorial(1)
4. faktorial(1) = 1 * faktorial(0)
5. faktorial(0) = 1 // akhir rekursi

Beberapa hal yang perlu diperhatikan dalam penerapan rekursi

Penghenti rekursi
Proses dalam rekursi harus ada titik akhir. Titik akhir disini merupakan batas dari fungsi untuk tidak lagi memanggil dirinya sendiri sekaligus awal dari proses pemberian nilai pada fungsi tersebut. Dari contoh diatas, fungsi faktorial tidak lagi memanggil dirinya sendiri saat n=0.

Penggunaan memori
Komputer mempunyai ruang memori yang terbatas. Setiap kali fungsi memanggil dirinya sendiri, ia memerlukan tambahan sejumlah memori. Jika proses ini terus menerus, pada akhirnya menyebabkan error StackOverflowException.

Efisiensi
Kita hampir selalu dapat menggantikan rekursi dengan loop. Loop tidak memiliki overhead dari pelewatan argumen, inisialisasi penyimpanan tambahan, dan pengembalian nilai. Kinerja program dapat lebih baik tanpa pemanggilan fungsi yang rekursif.