06. Fungsi

Fungsi adalah potongan kode yang diberi nama, bisa dipanggil berkali-kali, dan bisa diuji sendiri. Di OSN, fungsi dipakai untuk memecah soal menjadi bagian-bagian kecil yang masing-masing mudah dipastikan benar.

Bentuk sebuah fungsi

int kuadrat(int x) {
    return x * x;
}

int main() {
    cout << kuadrat(5) << "\n";   // 25
    return 0;
}

Bagian-bagiannya:

Yang terjadi saat kuadrat(5) dipanggil, berurutan:

1. Nilai 5 disalin ke dalam parameter x.
2. Pengerjaan main berhenti sementara, dan pengerjaan berpindah ke dalam kuadrat.
3. return x * x; menghitung 25 dan mengirimkannya kembali.
4. Pengerjaan kembali ke main, tepat di tempat pemanggilan tadi, dan seluruh tulisan kuadrat(5) digantikan nilai 25.

Karena itu pemanggilan fungsi boleh diletakkan di mana pun sebuah nilai boleh berada: di dalam cout, di dalam if, bahkan sebagai masukan fungsi lain seperti kuadrat(kuadrat(2)).

return juga langsung mengakhiri fungsinya. Baris apa pun sesudah return yang sudah dijalankan tidak akan dikerjakan:

int uji(int n) {
    if (n < 0) return -1;      // langsung keluar
    return n * 2;              // hanya tercapai kalau n >= 0
}

Sifat ini dipakai untuk keluar lebih awal dari fungsi pemeriksa, dan akan sering kamu lihat pada bool prima(...) di PR bab ini.

Fungsi harus ditulis di atas tempat ia dipanggil, atau dideklarasikan lebih dulu:

int kuadrat(int x);      // deklarasi (prototipe)

int main() {
    cout << kuadrat(5) << "\n";
}

int kuadrat(int x) {     // definisi, boleh di bawah
    return x * x;
}

Fungsi tanpa nilai kembali

Kalau fungsi hanya mengerjakan sesuatu (biasanya mencetak), tipenya void:

void garis(int panjang) {
    for (int i = 0; i < panjang; i++) cout << "-";
    cout << "\n";
}

Beberapa parameter

int maksimum(int a, int b) {
    return (a > b) ? a : b;
}

bool di_dalam(int x, int bawah, int atas) {
    return x >= bawah && x <= atas;
}

Fungsi yang mengembalikan bool sangat berguna: namanya menjelaskan maksud kondisi, sehingga if (di_dalam(x, 1, 100)) langsung terbaca.

Variabel lokal dan cakupan

Variabel yang dibuat di dalam fungsi hanya hidup di dalam fungsi itu.

void f() {
    int x = 10;     // hanya ada di dalam f
}

int main() {
    // cout << x;   // error: 'x' was not declared in this scope
}

Hal yang sama berlaku untuk blok { ... } di dalam if atau for: variabel i pada for (int i = ...) tidak ada setelah perulangan selesai.

Karena namanya tidak bertabrakan, dua fungsi boleh memakai nama variabel yang sama tanpa saling mengganggu. int i di dalam f dan int i di dalam main adalah dua kotak yang sama sekali berbeda.

Kebalikannya adalah variabel global: variabel yang ditulis di luar semua fungsi, sehingga bisa dibaca dan diubah dari mana saja.

const int MAKS = 100005;
int a[MAKS];        // global: dipakai bersama oleh semua fungsi
int n;

int jumlah() {
    int total = 0;  // lokal: hanya ada selama fungsi ini berjalan
    for (int i = 0; i < n; i++) total += a[i];
    return total;
}

Di perangkat lunak besar, variabel global dihindari karena membuat kode sulit ditelusuri. Di lomba, justru itu yang dipakai untuk array besar dan untuk nilai yang dibutuhkan semua fungsi — kodenya jadi lebih pendek dan tidak ada vector besar yang tersalin bolak-balik.

Nilai salinan dan referensi

Secara bawaan, parameter dikirim sebagai salinan. Mengubahnya di dalam fungsi tidak mengubah variabel asli:

void tambah_salah(int x) { x += 100; }

int a = 5;
tambah_salah(a);
cout << a << "\n";      // tetap 5

Tanda & membuat parameter menjadi referensi — nama lain untuk variabel aslinya:

void tambah_benar(int &x) { x += 100; }

int a = 5;
tambah_benar(a);
cout << a << "\n";      // 105

Perbedaannya bisa dibaca seperti ini: tanpa &, fungsi menerima fotokopi; dengan &, fungsi menerima kotak aslinya.

Referensi adalah cara memulangkan lebih dari satu nilai dari sebuah fungsi, karena return hanya bisa memulangkan satu:

void bagi(int a, int b, int &hasil, int &sisa) {
    hasil = a / b;
    sisa = a % b;
}

Rekursi

Fungsi boleh memanggil dirinya sendiri. Bentuk ini disebut rekursi, dan setiap fungsi rekursif butuh dua hal:

1. Kasus dasar — kondisi berhenti, tanpa pemanggilan lagi.
2. Langkah mengecil — pemanggilan pada soal yang lebih kecil.

long long faktorial(int n) {
    if (n <= 1) return 1;          // kasus dasar
    return n * faktorial(n - 1);   // langkah mengecil
}

Menelusuri faktorial(4):

faktorial(4) = 4 * faktorial(3)
             = 4 * 3 * faktorial(2)
             = 4 * 3 * 2 * faktorial(1)
             = 4 * 3 * 2 * 1
             = 24

Yang membuat rekursi bisa bekerja adalah tumpukan pemanggilan (call stack): setiap pemanggilan menyimpan variabel lokalnya sendiri dan tempat ia harus kembali. Saat faktorial(4) sedang menunggu faktorial(3), keduanya ada di memori sekaligus, masing-masing dengan n sendiri:

faktorial(4)   n = 4   menunggu faktorial(3)
  faktorial(3) n = 3   menunggu faktorial(2)
    faktorial(2) n = 2 menunggu faktorial(1)
      faktorial(1) n = 1 -> kembalikan 1
    kembalikan 2 * 1 = 2
  kembalikan 3 * 2 = 6
kembalikan 4 * 6 = 24

Bacanya: turun ke dalam sampai mengenai kasus dasar, lalu naik kembali sambil mengalikan. Setengah bagian atas adalah "memecah menjadi soal yang lebih kecil", setengah bagian bawah adalah "menggabungkan jawabannya".

Ketika rekursi menjadi lambat

Fungsi Fibonacci ditulis rekursif dengan sangat mudah:

long long fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

Tetapi cobalah fib(45): komputermu akan berpikir lama sekali. Sebabnya terlihat kalau pemanggilan fib(5) digambar sebagai pohon:

                    fib(5)
              /              \
          fib(4)             fib(3)
         /      \           /      \
     fib(3)    fib(2)    fib(2)   fib(1)
     /    \    /    \    /    \
 fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
  /  \
fib(1) fib(0)

fib(3) muncul dua kali, fib(2) tiga kali, fib(1) lima kali — seluruh cabangnya dihitung ulang dari nol setiap kali. Jumlah pemanggilannya tumbuh seperti deret Fibonacci itu sendiri:

Setiap kenaikan n sebesar 5 melipatgandakan pekerjaannya sekitar sebelas kali.

Bandingkan dengan versi perulangan yang hanya menyimpan dua nilai terakhir:

long long fib_cepat(int n) {
    long long a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        long long c = a + b;
        a = b;
        b = c;
    }
    return a;
}

Bedanya bukan sedikit: untuk n = 45, versi rekursif mengerjakan 3,67 miliar pemanggilan fungsi (beberapa detik sampai belasan detik, tergantung komputernya), sedangkan versi perulangan cukup 45 putaran dan selesai sebelum sempat terasa. Keduanya mencetak jawaban yang sama, 1134903170.

Yang dibuang versi perulangan bukan rekursinya, melainkan pengulangan pekerjaan. Persoalan "perhitungan yang sama dihitung berkali-kali" inilah yang diselesaikan dynamic programming di Bab 13 — dan tantangan PR bab ini adalah setengah langkah pertamanya.

Kenapa fungsi penting di lomba

• Menguji bagian kecil. bool prima(long long n) bisa dicoba dengan 1, 2, 9, dan 97 sebelum dipakai di soal besar.
• Mengurangi salah tulis. Logika yang dipakai tiga kali cukup ditulis sekali.
• Membuat kode terbaca saat waktu menipis. if (prima(x)) lebih cepat dipahami daripada tujuh baris perulangan di tengah main.

Pekerjaan rumah

Kesalahan yang paling sering

Tips OSN

Fungsi adalah alat menguji, bukan alat merapikan. Di lomba, keuntungan terbesar fungsi bukan kerapian kode melainkan kemampuan menguji satu bagian secara terpisah. bool prima(long long n) bisa dicoba dengan 1, 2, 9, dan 97 dalam sepuluh detik; logika yang sama yang tertanam di tengah main hanya bisa diuji lewat seluruh soal.

Rekursi punya batas kedalaman. Setiap pemanggilan fungsi menyimpan datanya di stack, dan stack yang habis membuat program berhenti sendiri — dinilai Runtime Error, bukan Wrong Answer. Rekursi sedalam 10⁶ pemanggilan hampir pasti gagal. Kalau kedalamannya sebanding dengan N dan N bisa mencapai 10⁵ atau lebih, ubah rekursinya menjadi perulangan.

Rekursi tanpa dasar tidak akan berhenti. Setiap fungsi rekursif harus punya dua bagian: kasus dasar yang berhenti, dan pemanggilan yang bergerak menuju kasus dasar. Kalau salah satu hilang, gejalanya sama dengan perulangan tak berujung.

Hitung dulu berapa kali fungsinya dipanggil. Rekursi yang memanggil dirinya dua kali untuk setiap tingkat membuat jumlah pemanggilan berlipat ganda. fib(45) versi naif memerlukan 3,67 miliar pemanggilan — bandingkan dengan aturan 10⁸ operasi per detik di Bab 05. Kalau angkanya tidak masuk akal, penyelesaiannya memang harus diganti, bukan dioptimalkan sedikit.

Parameter besar dikirim dengan referensi. Mengirim vector sepanjang 10⁶ sebagai salinan berarti menyalin 10⁶ elemen setiap pemanggilan. Tanda & pada parameter menghilangkan biaya itu sama sekali. Ini baru terasa mulai Bab 07, tetapi kebiasaannya dibentuk sekarang.

Beberapa fungsi pustaka yang menghemat waktu ketik:

Ringkasan

• Fungsi punya tipe hasil, nama, parameter, dan return. void untuk fungsi yang tidak memulangkan nilai.
• return langsung mengakhiri fungsi; pemanggilannya digantikan nilai yang dipulangkan.
• Variabel lokal hanya hidup di dalam blok tempat ia dibuat. Array besar di lomba dibuat global.
• Tanpa & parameter diterima sebagai salinan; dengan & fungsi bekerja pada variabel aslinya — dipakai untuk memulangkan lebih dari satu nilai dan untuk menghindari penyalinan vector besar.
• Fungsi rekursif wajib punya kasus dasar dan langkah yang mengecil.
• Rekursi yang menghitung ulang submasalah yang sama bisa sangat lambat; menyimpan hasilnya (memoization) adalah pintu masuk ke Bab 13.

Latihan bergaya OSN

Ketiga soal berikut meminta jawabannya dipecah menjadi fungsi. Tulis fungsinya lebih dulu, uji sendiri dengan beberapa angka, baru sambungkan ke main.

Kerangka ketiganya ada di exercises/06/osn/.

Soal 1 — Akar Digit

Akar digit sebuah bilangan didapat dengan menjumlahkan semua digitnya, lalu mengulangi langkah yang sama terhadap hasilnya, sampai tersisa satu digit saja.

Format masukan. Baris pertama berisi bilangan bulat T, banyaknya kasus uji. T baris berikutnya masing-masing berisi satu bilangan bulat N.

Format keluaran. T baris berisi akar digit setiap N.

Batasan.

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 10¹⁸

Contoh masukan

3
9875
9
1000000000000000000

Contoh keluaran

2
9
1

Penjelasan. Untuk 9875: 9 + 8 + 7 + 5 = 29, lalu 2 + 9 = 11, lalu 1 + 1 = 2. Bilangan yang sudah satu digit langsung menjadi jawabannya sendiri.

Kerangkanya: exercises/06/osn/01-akar-digit.cpp

Soal 2 — Menara Hanoi

Ada tiga tiang bernama A, B, dan C. Pada tiang A tersusun N cakram dengan ukuran berbeda, terbesar di bawah dan terkecil di atas. Seluruh cakram harus dipindahkan ke tiang C dengan dua aturan:

• satu kali perpindahan hanya boleh memindahkan satu cakram, yaitu cakram paling atas dari salah satu tiang;
• cakram besar tidak boleh diletakkan di atas cakram yang lebih kecil.

Cetak urutan perpindahan yang menyelesaikan susunan itu dengan jumlah perpindahan sesedikit mungkin.

Format masukan. Satu baris berisi bilangan bulat N.

Format keluaran. Baris pertama berisi banyaknya perpindahan. Setiap baris berikutnya berisi dua huruf tiang: tiang asal dan tiang tujuan, dipisahkan satu spasi.

Batasan. 1 ≤ N ≤ 15.

Contoh masukan

2

Contoh keluaran

3
A B
A C
B C

Penjelasan. Cakram kecil dipindahkan ke B supaya cakram besar bisa pindah ke C, lalu cakram kecil menyusul. Banyaknya perpindahan paling sedikit selalu 2^N − 1.

Kerangkanya: exercises/06/osn/02-menara-hanoi.cpp

Soal 3 — Bilangan Sempurna

Faktor sejati sebuah bilangan adalah semua faktor positifnya kecuali bilangan itu sendiri. Sebuah bilangan disebut sempurna kalau jumlah faktor sejatinya sama dengan bilangan itu, berlebih kalau jumlahnya lebih besar, dan kurang kalau jumlahnya lebih kecil.

Format masukan. Baris pertama berisi bilangan bulat T. T baris berikutnya masing-masing berisi satu bilangan bulat N.

Format keluaran. T baris berisi SEMPURNA, BERLEBIH, atau KURANG.

Batasan.

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 10⁹

Contoh masukan

4
6
12
8
1

Contoh keluaran

SEMPURNA
BERLEBIH
KURANG
KURANG

Penjelasan. Faktor sejati 6 adalah 1, 2, dan 3, yang berjumlah 6. Faktor sejati 12 adalah 1, 2, 3, 4, 6, yang berjumlah 16 — lebih besar daripada 12. Faktor sejati 8 adalah 1, 2, 4, berjumlah 7. Bilangan 1 tidak punya faktor sejati sama sekali, jadi jumlahnya 0.

Kerangkanya: exercises/06/osn/03-bilangan-sempurna.cpp

Bingung atau sudah selesai? Buka halaman pembahasan PR.