Apa itu Recursion ?

oleh -82 views
recursion

Apa itu Recursion?
Proses di mana suatu fungsi memanggil dirinya sendiri secara langsung atau tidak langsung disebut rekursi dan fungsi yang sesuai di sebut sebagai fungsi rekursif. Kemudian Menggunakan algoritma rekursif, masalah tertentu dapat di selesaikan dengan cukup mudah. Contoh masalah tersebut adalah Towers of Hanoi (TOH), Inorder/Preorder/Postorder Tree Traversals, DFS of Graph, dll. (Dheva)

Interpretasi Matematika

Mari kita pertimbangkan masalah yang harus di tentukan oleh seorang programmer untuk menentukan jumlah n bilangan asli pertama, ada beberapa cara untuk melakukannya tetapi pendekatan yang paling sederhana adalah dengan menambahkan angka mulai dari 1 hingga n. Jadi fungsinya hanya terlihat seperti,

approach(1) – Simply adding one by one

f(n) = 1 + 2 + 3 +……..+ n

but there is another mathematical approach of representing this,

approach(2) – Recursive adding 

f(n) = 1                  n=1

f(n) = n + f(n-1)    n>1

Ada perbedaan sederhana antara pendekatan (1) dan pendekatan (2) dan itu dalam pendekatan (2) fungsi ” f( ) ” itu sendiri di panggil di dalam fungsi, sehingga fenomena ini di sebut sebagai rekursi dan fungsi yang mengandung rekursi di sebut fungsi rekursif, pada akhirnya ini adalah alat yang hebat di tangan programmer untuk mengkodekan beberapa masalah dengan cara yang jauh lebih mudah dan efisien.

Kemudian Apa kondisi dasar dalam rekursi?
Dalam program rekursif, solusi untuk kasus dasar di sediakan dan solusi dari masalah yang lebih besar di nyatakan dalam bentuk masalah yang lebih kecil.

int fact(int n)
{
    if (n < = 1) // base case
        return 1;
    else    
        return n*fact(n-1);    
}

Dalam contoh di atas, kasus dasar untuk n < = 1 didefinisikan dan nilai bilangan yang lebih besar dapat diselesaikan dengan mengonversi ke yang lebih kecil sampai kasus dasar tercapai.

Kemudian Bagaimana masalah tertentu di selesaikan menggunakan rekursi?
Idenya adalah untuk mewakili masalah dalam satu atau lebih masalah yang lebih kecil, dan menambahkan satu atau lebih kondisi dasar yang menghentikan rekursi. Misalnya, kita menghitung faktorial n jika kita mengetahui faktorial dari (n-1). Kasus dasar untuk faktorial adalah n = 0. Kami mengembalikan 1 ketika n = 0.

Mengapa kesalahan Stack Overflow terjadi dalam rekursi?
Jika kasus dasar tidak tercapai atau tidak di tentukan, maka masalah stack overflow mungkin muncul. Mari kita ambil contoh untuk memahami hal ini.

int fact(int n)
{
    // wrong base case (it may cause
    // stack overflow).
    if (n == 100) 
        return 1;

    else
        return n*fact(n-1);
}

Tinggalkan Balasan

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *