Lewati ke konten utama
Numekara
Konsultasi GratisKontak

K1 · Modul 03

Rekursi dan induksi

47 langkah singkat, dari mudah sampai tantangan.

  1. Level 1

    Kenal

  2. Level 2

    Paham

  3. Level 3

    Terapkan

  4. Level 4

    Tantangan

  5. Level 5

    Pendalaman

Intinya

  • Rekursi yang benar butuh kasus dasar, kemajuan menuju kasus dasar, dan "percaya pada rekursi" untuk masukan yang lebih kecil.
  • Induksi (basis + langkah) membuktikan fungsi rekursif benar; rekursi dan induksi adalah gagasan yang sama.
  • Pohon rekursi dan rekurensi memberi biayanya; teorema master membandingkan a dengan bᵈ.
  • Memo (buatan sendiri atau functools.cache) menghapus submasalah yang dihitung berulang.
  • Kedalaman rekursi adalah ruang tumpukan; batas bawaan Python sekitar 1.000 tingkat.

Sebelum mulai

±4 jam.

Modul ini memakai materi di bawah. Belum yakin? Ulas dulu bagian yang disebut.

Hasil belajar: merancang fungsi rekursif yang benar; membuktikan pernyataan dan fungsi rekursif dengan induksi; menghitung banyak panggilan dengan pohon rekursi; menulis dan menyelesaikan rekurensi, termasuk dengan intuisi teorema master; menghapus perhitungan berulang dengan memo buatan sendiri lalu functools.cache; menjelaskan batas rekursi sebagai ruang tumpukan; serta menjelajah peta Kurir Makmur secara rekursif.

Proyek: Kurir Makmur langkah 3: jangkau_rekursif (kontrak Proyek Kurir §3).

Istilah di modul ini (24)

Ketuk istilah untuk melihat penjelasannya. Di materi, istilah bergaris titik membuka kartu yang sama. Semua istilah course

Bahan modul

Semua kode, latihan, dan data modul ini dalam satu zip, untuk dijalankan di laptop atau Google Colab.

  • 30 contoh kode
  • 9 berkas latihan + tes
  • 1 berkas data
Semua data course (data-k1.zip) Cara menjalankan di laptop
Lihat isi zip
  • BACA-DULU.txt
  • contoh_k1_03_43.py
  • contoh_k1_03_63.py
  • contoh_k1_03_92.py
  • contoh_k1_03_120.py
  • contoh_k1_03_150.py
  • contoh_k1_03_271.py
  • contoh_k1_03_284.py
  • contoh_k1_03_330.py
  • contoh_k1_03_398.py
  • contoh_k1_03_541.py
  • contoh_k1_03_608.py
  • contoh_k1_03_653.py
  • contoh_k1_03_692.py
  • contoh_k1_03_721.py
  • contoh_k1_03_750.py
  • contoh_k1_03_1066.py
  • contoh_k1_03_1218.py
  • contoh_k1_03_1298.py
  • contoh_k1_03_1351.py
  • contoh_k1_03_1387.py
  • contoh_k1_03_1512.py
  • contoh_k1_03_1544.py
  • contoh_k1_03_1575.py
  • contoh_k1_03_1606.py
  • contoh_k1_03_1784.py
  • contoh_k1_03_1812.py
  • contoh_k1_03_1964.py
  • contoh_k1_03_2189.py
  • contoh_k1_03_2217.py
  • contoh_k1_03_2259.py
  • test_k1_03_1.py
  • test_k1_03_2.py
  • test_k1_03_4.py
  • test_k1_03_8.py
  • test_k1_03_5.py
  • test_k1_03_3.py
  • test_k1_03_6.py
  • test_k1_03_7.py
  • test_k1_03_9.py
  • peta.json