Definisi yang menunjuk dirinya

Menghitung tanpa menghitung

Perhatikan apa yang membuat antrean itu berhenti. Bukan aturan tambahan, melainkan satu orang yang tidak punya orang di depannya dan karena itu dapat menjawab tanpa bertanya. Orang itu ujungnya, dan tanpa dia pertanyaannya berjalan selamanya.

IngatRekursi adalah definisi yang menyebut dirinya sendiri untuk kasus yang lebih kecil, ditambah minimal satu kasus yang dijawab tanpa menyebut dirinya lagi.

Base case lebih dulu

Kasus yang dijawab langsung disebut base case. Ia bukan tambahan di akhir; ia syarat. Rekursi tanpa base case adalah bentuk lain dari loop abadi pada pelajaran 3.5, dan bentuknya persis sama: nilai yang dipakai untuk berhenti tidak pernah mencapai titik berhentinya.

Faktorial punya dua base case, dan keduanya bernilai satu. Faktorial satu bernilai satu karena mengalikan satu bilangan hanya menghasilkan bilangan itu. Faktorial nol juga bernilai satu, dan itu bukan kesepakatan aneh: satu adalah nilai netral perkalian, sama seperti nol nilai netral penjumlahan yang sudah dibahas pada pelajaran 1.2.

faktorial(value):
  IF value <= 1
    RETURN 1
  END
  RETURN value * faktorial(value - 1)

Base casenya memakai lebih kecil atau sama dengan satu, bukan sama dengan satu saja. Satu perbandingan menangani nol dan satu sekaligus, dan itu pola yang sama dengan penjaga pada pelajaran 3.5. Kalau ditulis sama dengan satu saja, faktorial nol akan melewati base casenya lalu memanggil faktorial negatif satu, dan dari situ menyusut selamanya menjauh dari base casenya.

Menyusut ke arah yang benar

  IF value <= 1
    RETURN 1
  END
  RETURN value * faktorial(value)

  IF value <= 1
    RETURN 1
  END
  RETURN value * faktorial(value - 1)

Dua syarat itu pantas dihafal sebagai pasangan. Ada kasus yang dijawab tanpa memanggil diri lagi, dan setiap pemanggilan bergerak menuju kasus itu. Salah satu hilang, rekursinya tidak berhenti.

Melihat jawaban naik kembali

Bagian yang paling sering keliru dibayangkan: perkaliannya tidak terjadi saat memanggil, melainkan saat jawaban kembali. Pemanggilan turun sampai base case lebih dulu, dan baru sesudah itu hasilnya dikalikan naik satu per satu.

faktorial(value):
  IF value <= 1
    RETURN 1
  END
  RETURN value * faktorial(value - 1)

Perhatikan kolom kedalaman. Ia naik sampai empat lalu turun kembali, dan itu bukan hiasan: setiap pemanggilan yang belum selesai benar benar tersimpan, menunggu jawaban dari yang di bawahnya. Struktur yang menyimpannya adalah stack, persis yang dipelajari pada pelajaran sebelumnya. Rekursi adalah stack yang dikelola untuk Anda alih alih ditulis sendiri.

Rekursi dan loop

Faktorial dapat ditulis sebagai loop biasa, dengan akumulator bernilai awal satu yang dikalikan dari satu sampai nilainya. Hasilnya sama persis. Yang berbeda hanya bentuk pikirannya: loop menaiki tangga dari bawah, rekursi menuruninya lalu naik kembali. Tidak ada yang lebih benar di antara keduanya untuk soal ini.

• Nilai awal akumulator pada versi loop adalah satu, bukan nol. Mengali dengan nol menghapus seluruh hasilnya.
• Kedalaman rekursi memakai memori. Rekursi sedalam ratusan ribu dapat menghabiskan ruang stack program, sedangkan loop tidak.
• Rekursi menang ketika persoalannya sendiri berbentuk bersarang, misalnya menelusuri pohon direktori. Untuk menghitung faktorial, keduanya sama saja.

Periksa pemahaman

Ringkasan

• Rekursi menyelesaikan persoalan dengan menyebut versi yang lebih kecil dari persoalan yang sama.
• Dua syarat, keduanya wajib: ada kasus yang dijawab tanpa memanggil diri, dan setiap pemanggilan bergerak menuju kasus itu.
• Base case bukan tambahan di akhir. Tanpanya rekursi adalah loop abadi berganti bentuk.
• Pakai lebih kecil atau sama dengan pada base case, supaya nilai di bawah titik mulai tidak melewatinya.
• Perkaliannya terjadi saat jawaban kembali, bukan saat memanggil.
• Pemanggilan yang menunggu tersimpan di stack. Rekursi adalah stack yang dikelola untuk Anda.
• Faktorial nol bernilai satu, sebab satu adalah nilai netral perkalian.