Pertukaran Rekursif dan Iteratif
Ubah faktorial dan Fibonacci rekursif menjadi loop iteratif, lalu jelaskan kapan batas rekursi dan ukuran tumpukan Python membuat iterasi lebih baik.
Pertukaran Rekursif dan Iteratif adalah pelajaran Coding 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 Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Dualitas Rekursif-Iteratif
Setiap algoritme yang dapat ditulis secara rekursif juga dapat ditulis secara iteratif, dan sebaliknya. Versi rekursif sering kali lebih mencerminkan definisi matematis masalah, sedangkan versi iteratif memberi Anda kendali eksplisit atas memori dan menghindari risiko luapan tumpukan. Memilih di antara keduanya merupakan keputusan pragmatis yang didasarkan pada keterbacaan, batas kedalaman, dan persyaratan kinerja.
Dalam wawancara, kemampuan untuk menyajikan kedua versi dan menjelaskan komprominya merupakan tanda kuat bahwa Anda telah menguasai materi.
factorial: Rekursif vs Iteratif
factorial adalah contoh klasik. Versi rekursif secara langsung menyandikan definisi matematis n! = n × (n-1)!. Versi ini menggunakan ruang tumpukan O(n) karena terdapat n nilai pengembalian yang tertunda. Versi iteratif melakukan perulangan dari 1 hingga n dengan ruang O(1). Untuk n = 1000, versi rekursif mencapai batas bawaan Python; versi iteratif dapat menangani n sebesar apa pun.
def factorial_rec(n):
if n == 0:
return 1
return n * factorial_rec(n - 1) # O(n) stack
def factorial_iter(n):
result = 1
for i in range(2, n + 1):
result *= i # O(1) stack
return result
print(factorial_rec(10)) # 3628800
print(factorial_iter(10)) # 3628800
# Large n: iterative works, recursive may overflow
print(factorial_iter(1000) > 0) # True (Python handles big ints)Fibonacci: Eksponensial vs Linear
Fibonacci rekursif naif memiliki time O(2^n)—sangat lambat untuk n yang besar. Versi iteratif memiliki time O(n) dan ruang O(1). Rekursi dengan memoisisasi (pelajaran berikutnya) juga memiliki time O(n), tetapi ruang O(n) karena kamus memo dan tumpukan O(n). Untuk Fibonacci, pendekatan iteratif optimal dalam semua metrik. Untuk n = 50, rekursi naif memerlukan waktu beberapa detik; versi iteratif memerlukan beberapa mikrodetik.
import time
def fib_rec(n):
if n <= 1: return n
return fib_rec(n-1) + fib_rec(n-2) # O(2^n)
def fib_iter(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a # O(n) time, O(1) space
# Timing comparison for n=35
start = time.time()
fib_rec(35)
print(f'Recursive n=35: {time.time()-start:.3f}s')
start = time.time()
fib_iter(35)
print(f'Iterative n=35: {time.time()-start:.6f}s')
print(fib_iter(100)) # handles large nPenelusuran Pohon: Rekursif dibandingkan Iteratif
Penelusuran pohon secara rekursif secara alami rapi karena struktur pohon mencerminkan rekursi. Namun, untuk pohon yang sangat miring (pada dasarnya berupa daftar tertaut), kedalaman rekursi sama dengan tinggi pohon = O(n), sehingga berisiko menyebabkan luapan tumpukan. Versi iteratif yang menggunakan tumpukan eksplisit tidak memiliki batas kedalaman dan memungkinkan ukuran tumpukan bertambah di area memori dinamis, bukan pada tumpukan pemanggilan.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val; self.left = left; self.right = right
def preorder_rec(root, result=None):
if result is None: result = []
if root:
result.append(root.val)
preorder_rec(root.left, result)
preorder_rec(root.right, result)
return result
def preorder_iter(root):
if not root: return []
result, stack = [], [root]
while stack:
node = stack.pop()
result.append(node.val)
if node.right: stack.append(node.right)
if node.left: stack.append(node.left)
return result
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(preorder_rec(root)) # [1, 2, 4, 5, 3]
print(preorder_iter(root)) # [1, 2, 4, 5, 3]Pengurutan Gabung: Rekursif dibandingkan Iteratif (Dari Bawah ke Atas)
Pengurutan gabung secara alami bersifat rekursif (membagi, memanggil secara rekursif, lalu menggabungkan). Pengurutan gabung iteratif dari bawah ke atas sepenuhnya menghindari rekursi: mulai dengan sublarik berukuran 1, gabungkan pasangan yang berdekatan menjadi sublarik berukuran 2, lalu berukuran 4, dan seterusnya, dengan menggandakan ukuran sublarik pada setiap lintasan. Pengurutan gabung dari bawah ke atas memiliki waktu O(n log n), ruang O(n) (untuk penyangga penggabungan), dan ruang tumpukan O(1).
def merge_sort_iterative(arr):
n = len(arr)
size = 1
while size < n:
for start in range(0, n, 2 * size):
mid = min(start + size, n)
end = min(start + 2 * size, n)
left = arr[start:mid]
right = arr[mid:end]
# Merge
i = j = 0
for k in range(start, end):
if i < len(left) and (j >= len(right) or left[i] <= right[j]):
arr[k] = left[i]; i += 1
else:
arr[k] = right[j]; j += 1
size *= 2
return arr
print(merge_sort_iterative([5, 2, 4, 6, 1, 3])) # [1,2,3,4,5,6]Saat Rekursi Jelas Lebih Baik
Rekursi sangat unggul ketika masalah memiliki struktur yang menyerupai pohon yang memetakan langsung ke graf pemanggilan, ketika kasus dasarnya alami, dan ketika kedalamannya terbatas (O(log n) untuk pohon seimbang dan pendekatan bagi-dan-taklukkan). Contohnya: penguraian JSON, penelusuran direktori, pohon permainan, dan masalah penelusuran mundur. Dalam kasus-kasus ini, kode rekursif lebih singkat, lebih jelas, dan lebih mudah dibuktikan kebenarannya daripada versi iteratif yang setara.
# Recursion is clearest for JSON-like nested structures
def flatten(nested):
result = []
for item in nested:
if isinstance(item, list):
result.extend(flatten(item)) # recurse on sub-list
else:
result.append(item)
return result
print(flatten([1, [2, [3, 4], 5], 6])) # [1, 2, 3, 4, 5, 6]
print(flatten([])) # []
print(flatten([[1, [2]], [3, [4, [5]]]])) # [1, 2, 3, 4, 5]Saat Iterasi Jelas Lebih Baik
Iterasi adalah pilihan yang tepat ketika: kedalamannya O(n) dan n besar (lebih dari sekitar 500 dalam kode Python yang aman), versi rekursif dan iteratif sama-sama mudah dibaca (Fibonacci, faktorial), atau masalahnya pada dasarnya berurutan tanpa penguraian alami menjadi submasalah. Perulangan sederhana yang memproses larik dari kiri ke kanan—jumlah berjalan, jendela geser, dua penunjuk—seharusnya selalu menggunakan iterasi.
# Iterative is clearest for sequential array processing
def running_max(nums):
result = []
curr_max = float('-inf')
for n in nums:
curr_max = max(curr_max, n)
result.append(curr_max)
return result
print(running_max([3, 1, 4, 1, 5, 9, 2, 6])) # [3,3,4,4,5,9,9,9]
# No natural recursion here — iteration is the only sensible choiceMengubah Rekursi DFS Menjadi Iterasi
Pendekatan sistematis: setiap DFS rekursif dapat diubah menjadi iteratif dengan mendorong argumen rekursif ke tumpukan eksplisit. Wawasan utamanya adalah bahwa pemanggilan rekursif f(args) setara dengan mendorong args lalu melakukan perulangan. Untuk pemrosesan pascaurutan (saat Anda memerlukan hasil dari anak sebelum induknya), Anda mungkin memerlukan pendekatan dua lintasan atau penanda kunjungan.
# Post-order iterative using two stacks
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val=val; self.left=left; self.right=right
def postorder_iter(root):
if not root: return []
s1, s2 = [root], []
while s1:
node = s1.pop()
s2.append(node.val)
if node.left: s1.append(node.left)
if node.right: s1.append(node.right)
return s2[::-1] # reverse gives post-order
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(postorder_iter(root)) # [4, 5, 2, 3, 1]Beban Tambahan Rekursi
Setiap pemanggilan rekursif dalam Python memiliki beban tambahan yang tidak sepele: bingkai baru dibuat (mengalokasikan memori di area memori dinamis), variabel lokal diinisialisasi, dan penunjuk alamat pengembalian disimpan. Tolok ukur menunjukkan bahwa beban tambahan pemanggilan fungsi dalam Python kira-kira 100–200 nanodetik per pemanggilan. Untuk kedalaman rekursi 10^6, ini terakumulasi menjadi 0,1–0,2 detik beban tambahan murni, terlepas dari pekerjaan algoritmanya. Perulangan iteratif sepenuhnya menghindari beban ini.
import time
def rec_sum(n):
if n == 0: return 0
return n + rec_sum(n - 1)
def iter_sum(n):
total = 0
for i in range(n + 1):
total += i
return total
import sys; sys.setrecursionlimit(10000)
n = 5000
start = time.time()
for _ in range(100): rec_sum(n)
print(f'Recursive sum({n}) x100: {(time.time()-start)*1000:.2f}ms')
start = time.time()
for _ in range(100): iter_sum(n)
print(f'Iterative sum({n}) x100: {(time.time()-start)*1000:.2f}ms')Menentukan Pilihan dalam Wawancara
Dalam wawancara pemrograman, jika Anda memiliki pilihan, tanyakan: 'Apakah kedalaman rekursi dibatasi oleh O(log n)?' Jika ya, rekursi tidak masalah. 'Apakah kedalaman rekursi O(n)?'—utamakan iterasi atau sebutkan bahwa Anda akan mengubahnya menjadi iteratif untuk penggunaan produksi. 'Apakah masalahnya secara alami berbentuk pohon atau menggunakan pendekatan bagi-dan-taklukkan?'—pilih pendekatan rekursif. 'Apakah masalahnya berupa pemindaian berurutan?'—gunakan iterasi.
Selalu nyatakan alasan Anda: 'Saya akan menggunakan rekursi di sini karena kedalamannya O(log n) untuk BST yang seimbang, sehingga ruang tumpukan O(log n) dapat diterima.'
Ringkasan: Tabel Kompromi
Merangkum komprominya: kode rekursif sering lebih singkat dan mencerminkan struktur masalah, tetapi memerlukan ruang tumpukan O(kedalaman) serta memiliki beban pemanggilan fungsi. Kode iteratif lebih panjang, tetapi menggunakan ruang tumpukan O(1) dan menghindari batas rekursi. Rekursi yang dimemoisasi (pelajaran berikutnya) adalah jalan tengah: mempertahankan kejelasan rekursi sekaligus menghilangkan perhitungan ulang yang tidak perlu. Selalu jelaskan kompleksitas ruang, termasuk ruang tumpukan pemanggilan, saat menganalisis solusi Anda.
rows = [
('Factorial', 'O(n) / O(1)', 'O(n) / O(1)', 'Same time; iter wins on space'),
('Fibonacci', 'O(2^n) / O(n)', 'O(n) / O(1)', 'Iter massively wins'),
('Binary search','O(log n) / O(log n)', 'O(log n) / O(1)', 'Iter wins on space'),
('Tree DFS', 'O(n) / O(h)', 'O(n) / O(h)', 'Equal; rec cleaner'),
('Merge sort', 'O(n log n) / O(log n)', 'O(n log n) / O(1)', 'BU-iter wins on stack'),
]
for name, rec, it, note in rows:
print(f'{name:<15} rec={rec:<22} iter={it:<22} {note}')Pemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Rangkuman Pelajaran
Dalam pelajaran ini Anda mempelajari: rekursi lebih disukai ketika kedalamannya O(log n) atau masalahnya secara alami berbentuk pohon; iterasi ketika kedalamannya O(n) atau masalahnya berurutan, Fibonacci rekursif naif adalah O(2^n)—versi iteratifnya memiliki waktu O(n) dan ruang O(1), dan setiap DFS rekursif dapat diubah menjadi iteratif dengan mengelola tumpukan eksplisit di area memori dinamis. Selanjutnya, kita menerapkan memoisasi untuk menghilangkan pemanggilan rekursif yang tidak perlu.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Pertukaran Rekursif dan Iteratif” gratis?
Ya — teks lengkap “Pertukaran Rekursif dan Iteratif” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Pertukaran Rekursif dan Iteratif”?
Ubah faktorial dan Fibonacci rekursif menjadi loop iteratif, lalu jelaskan kapan batas rekursi dan ukuran tumpukan Python membuat iterasi lebih baik. Kamu berlatih Coding 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 Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding 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 “Pertukaran Rekursif dan Iteratif” 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 Coding Interview Prep ini?
Ya. Setiap pelajaran Coding 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
- Kerangka Rekursi: Kasus Dasar, Kepercayaan, Pembangunan
- Memvisualisasikan Tumpukan Pemanggilan
- Pertukaran Rekursif dan Iteratif
- Memoization: Menyimpan Hasil Rekursif