Memahami Rekursi

Struktur Data dan Algoritma di Python

Miriam Antona

Software engineer

Definisi

  • Fungsi memanggil dirinya sendiri
  • Hampir semua situasi kita memakai loop
    • ganti loop dengan rekursi
  • Dapat menyelesaikan masalah yang awalnya tampak kompleks
Struktur Data dan Algoritma di Python

Contoh - faktorial

$n!$

Struktur Data dan Algoritma di Python

Contoh - faktorial

$n!=n$ · $(n-1)$ · $(n-2)$ · $...$ · $1$

$5!=$ $5$ · $4$ · $3$ · $2$ · $1=120$

def factorial(n):
  result = 1
  while n > 1:
    result = n * result
    n -= 1
  return result

factorial(5)

120
Struktur Data dan Algoritma di Python

Contoh - faktorial dengan rekursi

$n!= n$ · $(n-1)!$

def factorial_recursion(n):
  return n * factorial_recursion(n-1)
  • Berjalan selamanya!
Struktur Data dan Algoritma di Python

Contoh - mengidentifikasi kasus dasar

  • Tambahkan sebuah kondisi
    • memastikan algoritme tidak berjalan selamanya
  • Kasus dasar faktorial -> $n=1$
def factorial_recursion(n):
  if n == 1:

    return 1

  else:

    return n * factorial_recursion(n-1)

print(factorial_recursion(5))

120
Struktur Data dan Algoritma di Python

Cara kerja rekursi

  • Komputer memakai stack untuk melacak fungsi
    • Call stack
Struktur Data dan Algoritma di Python

Cara kerja rekursi

  • factorial(5) mulai
  • Sebelum factorial(5) selesai -> factorial(4) mulai
  • Sebelum factorial(4) selesai -> factorial(3) mulai

Gambar antrean dengan satu elemen yang mewakili sebuah fungsi.

Struktur Data dan Algoritma di Python

Cara kerja rekursi

  • factorial(5) mulai
  • Sebelum factorial(5) selesai -> factorial(4) mulai
  • Sebelum factorial(4) selesai -> factorial(3) mulai
  • Sebelum factorial(3) selesai -> factorial(2) mulai

Gambar antrean dengan dua elemen yang mewakili dua fungsi.

Struktur Data dan Algoritma di Python

Cara kerja rekursi

  • factorial(5) mulai
  • Sebelum factorial(5) selesai -> factorial(4) mulai
  • Sebelum factorial(4) selesai -> factorial(3) mulai
  • Sebelum factorial(3) selesai -> factorial(2) mulai
  • Sebelum factorial(2) selesai -> factorial(1) mulai

Gambar antrean dengan tiga elemen yang mewakili tiga fungsi.

Struktur Data dan Algoritma di Python

Cara kerja rekursi

  • factorial(5) mulai
  • Sebelum factorial(5) selesai -> factorial(4) mulai
  • Sebelum factorial(4) selesai -> factorial(3) mulai
  • Sebelum factorial(3) selesai -> factorial(2) mulai
  • Sebelum factorial(2) selesai -> factorial(1) mulai

Gambar antrean dengan empat elemen yang mewakili empat fungsi.

Struktur Data dan Algoritma di Python

Cara kerja rekursi

  • factorial(1) selesai
    • mengembalikan 1
  • factorial(2) selesai

Gambar antrean dengan empat elemen yang mewakili empat fungsi.

Struktur Data dan Algoritma di Python

Cara kerja rekursi

  • factorial(1) selesai
    • mengembalikan 1
  • factorial(2) selesai
    • mengembalikan 2

Gambar antrean dengan empat elemen yang mewakili empat fungsi. Fungsi terakhir disertai nilai kembalinya.

Struktur Data dan Algoritma di Python

Cara kerja rekursi

  • factorial(1) selesai
    • mengembalikan 1
  • factorial(2) selesai
    • mengembalikan 2
  • factorial(3) selesai
    • mengembalikan 6

Gambar antrean dengan tiga elemen yang mewakili tiga fungsi.

Struktur Data dan Algoritma di Python

Cara kerja rekursi

  • factorial(1) selesai
    • mengembalikan 1
  • factorial(2) selesai
    • mengembalikan 2
  • factorial(3) selesai
    • mengembalikan 6
  • factorial(4) selesai
    • mengembalikan 24

Gambar antrean dengan dua elemen yang mewakili dua fungsi.

Struktur Data dan Algoritma di Python

Cara kerja rekursi

  • factorial(1) selesai
    • mengembalikan 1
  • factorial(2) selesai
    • mengembalikan 2
  • factorial(3) selesai
    • mengembalikan 6
  • factorial(4) selesai
    • mengembalikan 24
  • factorial(5) selesai
    • mengembalikan 120

Gambar antrean dengan satu elemen yang mewakili satu fungsi.

Struktur Data dan Algoritma di Python

Cara kerja rekursi

  • factorial(1) selesai
    • mengembalikan 1
  • factorial(2) selesai
    • mengembalikan 2
  • factorial(3) selesai
    • mengembalikan 6
  • factorial(4) selesai
    • mengembalikan 24
  • factorial(5) selesai
    • mengembalikan 120

Gambar antrean kosong.

Struktur Data dan Algoritma di Python

Pemrograman dinamis

  • Teknik optimasi
  • Utamanya diterapkan pada rekursi
  • Dapat menurunkan kompleksitas algoritme rekursif
  • Digunakan untuk:
    • Masalah yang dapat dipecah jadi submasalah lebih kecil
    • Submasalah saling tumpang tindih
  • Solusi submasalah disimpan agar tidak menghitung ulang
    • Memoization
Struktur Data dan Algoritma di Python

Ayo berlatih!

Struktur Data dan Algoritma di Python

Preparing Video For Download...