Latihan: Tangga Rekursif

Studi Kasus

Sebuah gedung memiliki tangga dengan n anak tangga. Seorang pengunjung bisa melangkah 1 atau 2 anak tangga dalam satu langkah.

Tugasmu: buat program untuk menghitung berapa banyak cara berbeda pengunjung bisa mencapai anak tangga ke-n, menggunakan pendekatan rekursif.

Sebagai pemanasan, kamu juga akan mengimplementasikan fungsi faktorial secara rekursif sebelum mengerjakan masalah tangga.

Pola Rekursif Tangga

Perhatikan polanya: caraTangga(n) = caraTangga(n-1) + caraTangga(n-2). Mengapa demikian?

Karena untuk tiba di anak tangga ke-n, pengunjung pasti datang dari anak tangga n-1 (ambil 1 langkah) atau dari anak tangga n-2 (ambil 2 langkah). Kedua jalur ini saling bebas, sehingga dijumlahkan.

Yang Harus Dilakukan

1. faktorial — implementasikan fungsi rekursif: base case n == 0 kembalikan 1, rekursif kembalikan n * faktorial(n - 1).
2. caraTangga — implementasikan fungsi rekursif: base case n == 1 → 1, n == 2 → 2, rekursif kembalikan caraTangga(n-1) + caraTangga(n-2).
3. main sudah ditulis lengkap — jalankan dan pastikan output sesuai contoh.

Contoh Output yang Diharapkan

=== Tabel Faktorial ===
0! = 1
1! = 1
2! = 2
...
10! = 3628800

=== Tangga Rekursif ===
1 anak tangga  → 1 cara
2 anak tangga  → 2 cara
3 anak tangga  → 3 cara
...
10 anak tangga → 89 cara