Apa itu rekursi?

Berlatih Pertanyaan Wawancara Coding di Python

Kirill Smirnov

Data Science Consultant, Altran

Definisi

Rekursi adalah proses mendefinisikan masalah dengan merujuk dirinya sendiri
Rekursi adalah proses ketika fungsi memanggil dirinya sebagai subrutin

Contoh: Faktorial $n!$

$n! = n\cdot(n-1)\cdot(n-2)\cdot...\cdot1$

$n = 4$:

$4! = 4\cdot3\cdot2\cdot1$

4! = 24

Faktorial - Pendekatan Iteratif

$n! = n\cdot(n-1)\cdot(n-2)\cdot...\cdot1 = $

$ = 1\cdot2\cdot3\cdot...\cdot n$

Solusi iteratif:

# iterative factorial
def fact_iter(n):
    result = 1
    # looping over numbers from 1 to n
    for num in range(1, n+1)
        result = num * result

    return result

$n = 4:$

result = 1

result = 1 * result(1) = 1
result = 2 * result(1) = 2
result = 3 * result(2) = 6
result = 4 * result(4) = 24

$4! = 1 \cdot 2 \cdot 3 \cdot 4 = 24$

Faktorial - Pendekatan Rekursif

$n!$ $=n\cdot(n-1)!$

def fact_rec(n):
    return n * fact_rec(n-1)

Apa yang salah pada kode ini?

fact_rec(4)

RecursionError

Kita harus mendefinisikan kasus dasar!

$n! = n\cdot(n-1)\cdot(n-2)\cdot...\cdot1$

Kriteria berhenti / kasus dasar: $1! = 1$

def fact_rec(n):
    if n == 1:
        return 1
    return n * fact_rec(n-1)

fact_rec(4)

Ringkasan

Fungsi rekursif punya dua komponen utama:

pemanggilan rekursif ke versi masalah yang lebih kecil
kasus dasar yang mencegah pemanggilan tak hingga

Contoh - Pohon Keputusan

Pohon Keputusan

Klasifikasi dengan pohon keputusan

Menelusuri Pohon Keputusan

Menelusuri pohon keputusan

x - sampel baru $(x_1, x_2)$

# Pseudocode untuk menentukan kategori:

category = pred(node, x):

  # Cek apakah ada pemisahan
  if node.hasSplitting:

    # Tentukan anak simpul mana yang diambil
    if node.goToLeftChild(x):
      return pred(node.leftChild, x)   
    if node.goToRightChild(x):
      return pred(node.rightChild, x)

Menelusuri Pohon Keputusan

Prediksi dengan pohon keputusan

x - sampel baru $(x_1, x_2)$

# Pseudocode untuk menentukan kategori:

category = pred(node, x):

  # Cek apakah ada pemisahan
  if node.hasSplitting:

    # Tentukan anak simpul mana yang diambil
    if node.goToLeftChild(x):
      return pred(node.leftChild, x) 
    if node.goToRightChild(x):
      return pred(node.rightChild, x)

  # Mengembalikan kategori
  return node.category

Ayo berlatih!

Berlatih Pertanyaan Wawancara Coding di Python