🔄 Rekursi & Hubungan Rekurens

Definisi Rekursi

Rekursi adalah teknik pemrograman di mana sebuah fungsi memanggil dirinya sendiri untuk menyelesaikan masalah yang lebih kecil.

Komponen Utama

Setiap fungsi rekursif harus memiliki:

  • Base Case: Kondisi berhenti untuk mencegah rekursi tak terbatas
  • Recursive Case: Bagian yang memanggil fungsi itu sendiri

🎯 Contoh: Faktorial

function factorial(n) { // Base case if (n === 0) return 1; // Recursive case return n * factorial(n - 1); } // Contoh: factorial(5) = 5 * 4 * 3 * 2 * 1 = 120

📊 Hubungan Rekurens

Faktorial: $F(n) = n \cdot F(n-1)$ dengan $F(0) = 1$

Fibonacci: $F(n) = F(n-1) + F(n-2)$ dengan $F(0) = 0, F(1) = 1$

💡 Intinya:

Rekursi memecah masalah besar menjadi sub-masalah yang lebih kecil hingga mencapai kasus dasar yang dapat diselesaikan langsung.

🌳 Struktur Data Pohon

Definisi Pohon

Pohon adalah struktur data hierarkis yang terdiri dari node-node yang terhubung, dengan satu node akar (root) dan node-node anak (children).

Jenis-Jenis Pohon

  • Binary Tree: Setiap node maksimal memiliki 2 anak
  • Binary Search Tree (BST): Binary tree dengan aturan pengurutan
  • AVL Tree: BST yang seimbang secara otomatis

🎯 Binary Search Tree

Aturan BST:

  1. Semua node di subtree kiri lebih kecil dari root
  2. Semua node di subtree kanan lebih besar dari root
  3. Kedua subtree juga merupakan BST

⚡ Kompleksitas Operasi

Pencarian: O(log n) - Jika pohon seimbang

Insert/Delete: O(log n) - Jika pohon seimbang

Traversal: O(n) - Mengunjungi semua node