Rekursi dan Metode Pohon Rekursi
Telusuri pemanggilan rekursif dalam bentuk pohon, terapkan Teorema Master, dan turunkan kompleksitas waktu untuk merge sort, faktorial, serta variasi Fibonacci.
Rekursi dan Metode Pohon Rekursi adalah pelajaran DSA Interview Prep gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar DSA Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Rekursi dan Tumpukan Pemanggilan
Saat sebuah fungsi memanggil dirinya sendiri, setiap pemanggilan menambahkan bingkai tumpukan, yang menumpuk hingga kasus dasar tercapai lalu dilepaskan kembali. Membayangkan proses ini adalah langkah pertama untuk menganalisis rekursi.
def factorial(n):
if n == 0: # base case
return 1
return n * factorial(n - 1) # recursive call
# Call chain: factorial(4)
# 4 * factorial(3)
# 3 * factorial(2)
# 2 * factorial(1)
# 1 * factorial(0) -> 1
# Unwinds: 1, 2, 6, 24
print(factorial(5)) # 120Pohon Rekursi untuk Fibonacci
Sebuah pohon rekursi mengembangkan setiap pemanggilan menjadi subpemanggilannya. Fibonacci naif bercabang menjadi dua pada setiap langkah, sehingga membentuk pohon dengan sekitar 2^n simpul — yaitu O(2^n). Lihat kodenya.
call_count = [0]
def fib_naive(n):
call_count[0] += 1
if n <= 1:
return n
return fib_naive(n-1) + fib_naive(n-2)
for n in [5, 10, 15, 20]:
call_count[0] = 0
result = fib_naive(n)
print(f'fib({n})={result}, calls={call_count[0]}')
# Calls roughly double each time n increases by 1Mengenali Submasalah yang Berulang
Dalam pohon tersebut, pemanggilan yang sama seperti fib(3) berulang di berbagai cabang. Submasalah yang tumpang tindih ini merupakan tanda untuk menggunakan memoization, yang menyusutkan O(2^n) menjadi O(n).
# Memoised: each unique sub-problem computed once
def fib_memo(n, memo={}):
if n in memo: return memo[n]
if n <= 1: return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]
call_count2 = [0]
def fib_counted(n, memo={}):
call_count2[0] += 1
if n in memo: return memo[n]
if n <= 1: return n
memo[n] = fib_counted(n-1, memo) + fib_counted(n-2, memo)
return memo[n]
fib_counted(20)
print(f'calls with memo: {call_count2[0]}') # only 21Pohon Rekursi Pengurutan Gabung
Pohon pengurutan gabung memiliki tingkat sebanyak log n, dan setiap tingkat melakukan pekerjaan total O(n) — setiap elemen disentuh satu kali. Kalikan keduanya untuk mendapatkan O(n log n). Lihat kodenya.
# Merge sort: at each level, n total elements are merged
# Level 0: 1 merge of n elements -> n work
# Level 1: 2 merges of n/2 each -> n work
# Level 2: 4 merges of n/4 each -> n work
# ...log(n) levels...
# Total: n * log(n)
# Verify with operation counter:
def merge_sort_counted(arr):
ops = [0]
def _sort(a):
if len(a) <= 1: return a
m = len(a) // 2
l, r = _sort(a[:m]), _sort(a[m:])
result, i, j = [], 0, 0
while i < len(l) and j < len(r):
ops[0] += 1
if l[i] <= r[j]: result.append(l[i]); i+=1
else: result.append(r[j]); j+=1
return result + l[i:] + r[j:]
return _sort(arr), ops[0]
_, c = merge_sort_counted(list(range(64, 0, -1)))
print(f'Merge ops: {c}') # ~384 ~ 64*log2(64)=384Teorema Master
Teorema Master menyelesaikan T(n) = a*T(n/b) + O(n^d) dengan tiga kasus. Untuk pengurutan gabung (a=2, b=2, d=1), teorema ini menghasilkan O(n log n). Hafalkan ketiga kasus tersebut untuk ujian.
# Merge sort: T(n) = 2*T(n/2) + O(n)
# a=2, b=2, d=1, log_b(a)=log2(2)=1=d => O(n log n)
# Binary search: T(n) = 1*T(n/2) + O(1)
# a=1, b=2, d=0, log2(1)=0=d => O(log n)
# Strassen matrix mult: T(n) = 7*T(n/2) + O(n^2)
# a=7, b=2, d=2, log2(7)~2.81 > 2 => O(n^log2(7)) ~ O(n^2.81)
import math
print('log2(7) =', math.log2(7)) # 2.807...Menggambar Pohon Rekursi: Langkah demi Langkah
Untuk menggambar pohon rekursi: letakkan T(n) di bagian atas, kembangkan setiap pemanggilan, jumlahkan pekerjaan pada setiap tingkat, lalu kalikan dengan jumlah tingkat. Berlatihlah hingga proses ini menjadi otomatis.
# Factorial: T(n) = T(n-1) + O(1)
# Tree is a chain: n levels, O(1) each -> O(n)
# Fibonacci: T(n) = T(n-1) + T(n-2) + O(1)
# Binary tree of depth n, ~2^n nodes -> O(2^n)
# Merge sort: T(n) = 2*T(n/2) + O(n)
# Log levels, n work each -> O(n log n)
def count_recursive_calls(n, results=[]):
if n <= 1:
results.append(n)
return n
return count_recursive_calls(n-1, results) + count_recursive_calls(n-2, results)
results = []
count_recursive_calls(8, results)
print(f'fib(8) leaf calls: {len(results)}')Rekursi Eksponensial: Subset
Menghasilkan semua subset memiliki kompleksitas O(2^n) — jumlahnya tepat 2^n, jadi Anda tidak dapat membuatnya lebih cepat. Setiap elemen dapat masuk atau tidak masuk, sehingga terbentuk pohon biner pilihan. Lihat kodenya.
def subsets(nums):
result = []
def backtrack(start, current):
result.append(list(current)) # O(n) copy
for i in range(start, len(nums)):
current.append(nums[i])
backtrack(i + 1, current)
current.pop()
backtrack(0, [])
return result
nums = [1, 2, 3]
ss = subsets(nums)
print(len(ss)) # 8 = 2^3
print(ss)Rekursi Ekor dan Optimisasi
Rekursi ekor terjadi saat pemanggilan rekursif menjadi langkah terakhir. Beberapa bahasa menggunakan kembali bingkai untuk pemanggilan tersebut, tetapi Python tidak — sehingga rekursi yang dalam tetap dapat menyebabkan tumpukan meluap. Gunakan perulangan sebagai gantinya.
# Tail-recursive factorial (accumulator pattern)
def fact_tail(n, acc=1):
if n == 0:
return acc
return fact_tail(n - 1, n * acc) # tail call
# Python does NOT TCO, so this overflows for large n
# Instead, convert to iterative:
def fact_iter(n):
acc = 1
while n > 0:
acc *= n
n -= 1
return acc
print(fact_tail(10)) # 3628800
print(fact_iter(10)) # 3628800Kompleksitas Ruang pada Rekursi
Setiap pemanggilan rekursif menyimpan sebuah bingkai, sehingga rekursi memerlukan ruang sebesar O(kedalaman). Rekursi linear adalah O(n); DFS pada pohon seimbang adalah O(log n). Jika terlalu dalam, Anda akan mengalami RecursionError.
import sys
print(sys.getrecursionlimit()) # default 1000
# Increase limit for deep problems
sys.setrecursionlimit(10000)
# Track max depth manually
def max_depth_tracker(n, depth=0, max_seen=[0]):
max_seen[0] = max(max_seen[0], depth)
if n <= 0:
return
max_depth_tracker(n - 1, depth + 1, max_seen)
return max_seen[0]
print(max_depth_tracker(50)) # 50 => O(n) stack framesPohon Rekursi untuk Pengurutan Cepat
Pengurutan cepat memiliki kompleksitas O(n log n) dengan pivot yang baik, tetapi pivot yang buruk pada input terurut dapat menurunkannya menjadi O(n^2). Itulah alasan pengacakan pivot penting. Lihat kodenya.
import random
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = random.choice(arr) # randomised -> O(n log n) expected
less = [x for x in arr if x < pivot]
equal = [x for x in arr if x == pivot]
greater = [x for x in arr if x > pivot]
return quick_sort(less) + equal + quick_sort(greater)
print(quick_sort([3, 6, 8, 10, 1, 2, 1])) # sortedFungsi Pangkat: Rekursi Log n
Perhitungan naif x^n memerlukan O(n) perkalian, tetapi pengkuadratan membagi dua pekerjaan pada setiap langkah: x^n = (x^(n/2))^2. Hasilnya adalah O(log n) yang jelas — pembagian dua dalam praktik. Lihat kodenya.
def fast_pow(x, n):
if n == 0: return 1
if n < 0: return 1 / fast_pow(x, -n)
if n % 2 == 0:
half = fast_pow(x, n // 2)
return half * half # O(log n) calls
return x * fast_pow(x, n - 1)
print(fast_pow(2, 10)) # 1024
print(fast_pow(3, 5)) # 243
# Only log2(10)=3-4 recursive calls for n=10Pemeriksaan Singkat
Pemeriksaan singkat — tunjukkan apa yang telah diajarkan oleh metode pohon rekursi kepada Anda. Kerjakan dengan tenang, hanya ada satu pertanyaan. 🌳
Rangkuman Pelajaran
Rangkuman: pohon rekursi mengungkapkan total pekerjaan, Teorema Master menyelesaikan relasi rekursif bagi-dan-taklukkan, dan rekursi memerlukan ruang tumpukan O(kedalaman).
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Rekursi dan Metode Pohon Rekursi” gratis?
Ya — teks lengkap “Rekursi dan Metode Pohon Rekursi” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus DSA Interview Prep, upgrade ke CoddyKit PRO. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Rekursi dan Metode Pohon Rekursi”?
Telusuri pemanggilan rekursif dalam bentuk pohon, terapkan Teorema Master, dan turunkan kompleksitas waktu untuk merge sort, faktorial, serta variasi Fibonacci. Kamu berlatih DSA Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai DSA Interview Prep?
Tidak diperlukan pengalaman sebelumnya. DSA Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.
Berapa lama pelajaran “Rekursi dan Metode Pohon Rekursi” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran DSA Interview Prep ini?
Ya. Setiap pelajaran DSA Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Notasi Big-O dari Dasar
- Menganalisis Loop dan Loop Bersarang
- Rekursi dan Metode Pohon Rekursi
- Kompleksitas Ruang dan Pertukarannya