15 Desember 2021

Rekursi dan tumpukan (Recursion and stack)

Ayo kita kembali ke fungsi dan belajar tentanya lebih dalam lagi.

Topik pertama kita adalah rekursi.

Jika programming bukanlah hal baru untukmu, maka kamu mungkin familiar dan kamu bisa melewatkan bab ini.

Rekursi adalah pola programming yang sangat berguna didalam situasi dimana sebuah task bisa secara natural dibagi menjadi beberapa task yang memiliki jenis yang sama, tapi lebih sederhana. Atau ketika task bisa dibuat lebih sederhana menjadi sebuah aksi ditambah varian yang lebih sederhana dari beberapa task yang serupa.

ketika sebuah fungsi menyelesaikan sebuah task, didalam proses itu bisa memanggila beberapa fungsi lainnya. Sebagian kasus dari ini ketika sebuah fungsi memanggil dirinya sendiri. Itulah yang disebut rekursi.

Cara berfikir dua arah

Untuk sesuatu yang sederhana dimulai dengan ??? ayo kita buat sebuah fungsi pow(x, n) yang menaikan x dengan pangkat dari n. Dengan kata lain, mengkalikan x dengan dirinya sendiri sebanyak n kali.

pow(2, 2) = 4
pow(2, 3) = 8
pow(2, 4) = 16

Terdapat dua cara untuk mengimplementasikan hal itu.

  1. Pemikiran interaktif: perulangan for:

    function pow(x, n) {
      let result = 1;
    
      // kalikan hasil dari x n kali didalam perulangan
      for (let i = 0; i < n; i++) {
        result *= x;
      }
    
      return result;
    }
    
    alert( pow(2, 3) ); // 8
  2. Pemikiran rekursif: sederhanakan tugasnya dan panggil diri-sendiri:

    function pow(x, n) {
      if (n == 1) {
        return x;
      } else {
        return x * pow(x, n - 1);
      }
    }
    
    alert( pow(2, 3) ); // 8

Ingat baik-baik bagaimana varian rekursif secara dasar berbeda.

Ketika pow(x, n) dipanggil, eksekusinya dibagi menjadi dua cabang:

              if n==1  = x
             /
pow(x, n) =
             \
              else     = x * pow(x, n - 1)
  1. Jika n == 1, maka semuanya menjadi tidak penting. Itulah yang dipanggil dengan dasar dari rekursi, karena itu langsung menghasilkan nilai yang jelas pow(x, 1) sama dengan x.
  2. Sebaliknya, kita bisa merepresentasikan pow(x, n) sebagai x * pow(x, n - 1). Didalam matematika, satu akan ditulis xn = x * xn-1. Ini yang dipanggil dengan Langkah rekursif: kita mengubah tugas/task menjadi aksi yang lebih sederhana (perkalian dengan x) dan sebuah pemanggilan yang lebih sederhana dari tugas/task yang sama (pow dengan menurunkan n). Langkah selanjutnya menyederhanakan itu lebih jauh sampai n mencapai 1.

Kita bisa berkata bahwa pow *secara rekursif memanggil dirinya sendiri sampai n == 1.

Contoh, untuk mengkalkulasi pow(2, 4) varian rekursi melakukan langkah-langkah ini:

  1. pow(2, 4) = 2 * pow(2, 3)
  2. pow(2, 3) = 2 * pow(2, 2)
  3. pow(2, 2) = 2 * pow(2, 1)
  4. pow(2, 1) = 2

Jadi, rekursi mengurangi sebuah pemanggilan fungsi menjadi yang lebih sederhana, dan lalu ??? bahkan lebih sederhana, dan seterusnya, sampai hasilnya menjadi jelas.

Rekursi biasanya lebih pendek

Solusi rekursi biasanya lebih pendek daripada sebuah iterasi.

Disini kita bisa menulis ulang menggunakan operator konsional ? daripada if untuk membuat pow(x, n) lebih pendek dan tetap mudah dibaca:

function pow(x, n) {
  return (n == 1) ? x : (x * pow(x, n - 1));
}

Angka maksimal dari pemanggilan bercabang (termasuk yang pertama) dipanggil dengan kedalaman rekursi/recursion depth. Di kasus kita, itu akan persis n.

Maksimal kedalaman rekursi dibatasi oleh mesin Javascript. Kita bisa berkata bahwa itu mungkin 10000, beberapa mesin bisa lebih tapi 100000 mungkin sudah diluar batas dari kebanyakan mesin. Terdapat optimasi otomatis yang membantu meringankan ini(???optimasi tail calls???), tapi mereka belum sepenuhnya didukung di semuanya dan hanya bekerja pada kasus yang sederhana.

Itu membatasi aplikasi dari rekursi, tapi itu tetaplah cukup besar. Disana terdapat task dimana cara berfikir rekursif membuat kode lebih sederhana, dan lebih mudah diperlihara.

Konteks eksekusi dan tumpukan

Sekarang ayo kita membahas bagaimana pemanggilan rekursi bekerja. Untuk itu kita akan melihat isi dari fungsi.

Informasi tentang proses dari eksekusi dari sebuah fungsi yang berjalan disimpan didalam konteks eksekusinya.

Execution context adalah sebuah struktur data internal yang mengandung detail tentang eksekusinya dari sebuah fungsi: dimana alur kontrolnya adalah sekarang, variabel yang sekarang, nilai dari this (kita tidak akan mengunakan ini disini) dan beberapa detail internal lainnya.

Satu pemanggilan fungsi mempunyai tepat satu konteks eksekusi yang terkait dengannya.

Ketika sebuah fungsi melakukan pemanggilan bercabang, Hal berikut terjadi:

  • Fungsi yang sekarang dihentikan sementara ??? paused.
  • Konteks eksekusi yang terkait dengannya diingat dalam sebuah struktur data spesial dipanggil dengan tumpukan konteks eksekusi.
  • Pemanggilan bercabang dieksekusi.
  • Setelah itu selesai, eksekusi konteks yang lama diterima dari tumpukan, dan fungsi terluar dilanjutkan dari mana itu berhenti.

Ayo kita lihat apa yang terjadi selama pemanggilan pow(2, 3).

pow(2, 3)

Di awal pemanggilan pow(2, 3) konteks eksekusi akan menyimpan variabel: x = 2, n = 3, alur eksekusi berada pada baris 1 dari fungsi.

Kita bisa menggambarkannya seperti:

  • Context: { x: 2, n: 3, at line 1 } pow(2, 3)

Itu ketika fungsi mulai dieksekusi. Kondisinya n == 1 adalah false, jadi alurnya berlanjut ke cabang kedua dari if:

function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

alert( pow(2, 3) );

Variabelnya juga sama, tapi barisnya berubah, jadi konteksnya sekarang:

  • Context: { x: 2, n: 3, at line 5 } pow(2, 3)

Untuk mengkalkulasikan x * pow(x, n -1), kita perlu membuat subcall dari pow dengan argumen baru pow(2, 2).

pow(2, 2)

Untuk melakukan pemanggilan bercabang, javascript mengingat konteks eksekusi yang sekarang didalam tumpukan konteks eksekusi.

Disini kita memanggil fungsi yang sama pow, tapi itu tidaklah penting. Prosesnya sama untuk semua fungsi:

  1. Konteks yang sekarang telah ???mengingat??? tumpukan teratas.
  2. Konteks baru dibuat untuk subcall.
  3. Ketika subcall telah selesai ??? konteks sebelumnya dikeluarkan dari tumpukan, dan eksekusinya dilanjutkan.

Here???s the context stack when we entered the subcall pow(2, 2): Disini tumpukan konteks ketika kita memasuki subcallnya pow(2, 2);

  • Context: { x: 2, n: 2, at line 1 } pow(2, 2)
  • Context: { x: 2, n: 3, at line 5 } pow(2, 3)

Konteks eksekusi baru yang sekarang berada di atas (dan jelas), dan konteks yang sebelumnya berada dibawah.

Ketika kita menyelesaikan subcall ??? itu akan mudah untuk melanjutkan konteks sebelumnya, karena itu tetap menyimpan kedua variabel dan tempat yang tepat dimana kode itu berhenti.

Tolong dicatat:

Disini dialam gambar kita gunakan kata ???line???, sebagai contoh disana terdapat satu subcall didalam baris, tapi secara umum sebuah baris dari kode mungkin mengandung subcall ganda, seperti pow(???) + pow(???) + somethingElse(???).

Jadi itu harus menjadi lebih presisi untuk dikatakan eksekusi berlanjut ???langsung seterlah subcall???.

pow(2, 1)

Prosesnya diulangi: subcall baru dibuat pada baris 5, sekarang dengan argumen x=2, n=1.

Sebuah konteks eksekusi baru dibuat, yang sebelumnya didorong dari atas tumpukan:

  • Context: { x: 2, n: 1, at line 1 } pow(2, 1)
  • Context: { x: 2, n: 2, at line 5 } pow(2, 2)
  • Context: { x: 2, n: 3, at line 5 } pow(2, 3)

Disana terdapat 2 konteks lama sekarang dan 1 sedang berjalan untuk pow(2, 1).

Keluar

Selama eksekusi dari pow(2, 1), tidak seperti sebelumnya, kondisi n == 1 sekarang bernilai true, jadi cabang pertama dari if bekerja:

function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

Disana sekarang tidak ada lagi pemanggilan bercabang, jadi fungsinya selesai, mengembalikan 2.

Setelah fungsinya selesai, konteks eksekusinya tidak dibutuhkan lagi, jadi itu akan dihilangkan dari memori. Satu yang sebelumnya dikembalikan dari atas tumpukan:

  • Context: { x: 2, n: 2, at line 5 } pow(2, 2)
  • Context: { x: 2, n: 3, at line 5 } pow(2, 3)

Eksekusi dari pow(2, 2) dilanjutkan. Itu telah mempunyai hasil dari subcall pow(2, 1), jadi itu bisa menyelesaikan evaluasi dari x * pow(x, n - 1), mengembalikan 4.

Konteks sebelumnya dikembalikan:

  • Context: { x: 2, n: 3, at line 5 } pow(2, 3)

Ketika itu selesai, kita mempunyai hasil dari pow(2, 3) = 8.

Dalam kasus ini kedalaman rekursinya adalah: 3.

Seperti yang bisa kita lihat dari ilustrasi diatas, kedalaman rekursi sama dengan nilai maksimal dari konteks didalam tumpukan.

Catatan kebutuhan memori. Konteks memakan memori. Didalam kasus ini, menaikan dengan pangkat dari n sebenarnya membutuhkan memori sebanyak n konteks, untuk semua nilai terendah dari n.

Algoritma berbasis perulangan lebih menghemat memori:

function pow(x, n) {
  let result = 1;

  for (let i = 0; i < n; i++) {
    result *= x;
  }

  return result;
}

Interatif pow menggunakan konteks tunggal mengganti i dan result didalam prosesnya. Kebutuhan memorinya kecil, tidak berubah-ubah dan tidak tergantung kepada n.

Rekursi apapun bisa ditulis ulang sebagai perulangan. Varian perulangan biasanya bisa dibuat lebih efektif.

???Tapi terkadang menulis ulang bukanlah hal yang sepele, terutama ketika fungsi menggunakan pemanggilan rekursif yang berbeda tergantung dari kondisi dan menyatukan hasil mereka atau cabangnya lebih rumit. Dan optimasinya mungkin tidak dibutuhkan dan benar-benar menghabiskan tenaga.

Rekursi bisa memberikan kode yang lebih pendek, lebih mudah dimengerti dan didukung. Optimasi tidak dibutuhkan di setiap tempat, kebanyakan kita butuh kode yang bagus, itulah kenapa itu digunakan.

Rekursif traversal

Penerapan bagus lainnya dari rekursi adalah rekursif traversal.

Bayangkan, kita punya sebuah perusahaan. Struktur karyawannya bisa dipresentasikan sebagai sebuah objek:

let company = {
  sales: [{
    name: 'John',
    salary: 1000
  }, {
    name: 'Alice',
    salary: 1600
  }],

  development: {
    sites: [{
      name: 'Peter',
      salary: 2000
    }, {
      name: 'Alex',
      salary: 1800
    }],

    internals: [{
      name: 'Jack',
      salary: 1300
    }]
  }
};

Dengan kata lain, perusahaannya mempunyai departemen.

  • Sebuah departemen mungkin mempunyai sebuah array untuk staf. Contoh, departemen sales mempunyai dua karyawan John dan Alice.

  • Atau sebuah departemen mungkin dibagi menjadi sub-departemen, like development mempunyai dua cabang: sites dan internals. Untuk masin-masing memiliki stafnya masing-masing.

  • Hal yang mungkin terjadi adalah ketika sub-departemennya berkembang, itu akan terbagi menjadi sub-sub-departemen (tau tim).

    Contoh, departemen sites di masa depan mungkin akan terbagi menjadi tim siteA dan siteB. Dan mereka, memiliki kemungkinan, terbagi lagi. Itu bukanlah sebuah gambaran, hanya sesuatu yang bisa terfikirkan.

Sekarang kita ingin sebuah fungsi untuk mendapatkan jumlah dari seluruh gaji. Bagaiman kita melakukannya?

Sebuah pendekatan iteratif tidaklah mudah, karena strukturnya tidak sederhana. Pertama mungkin untuk membuat perulangan fordidalam company dengan sub-perulangan bercabang didalam departemen level 1. Tapi kita butuh lebih banyak sub-perulangan untuk mengiterasi staf didalam departemen level 2 seperti sites??? Dan lalu sub-perulangan lainnya didalam departemen level 3 yang mungkin muncul di masa mendatang? Jika kita menggunakan 3-4 sub-perulangan didalam kode untuk menjelajahi objek tunggal, itu akan terlihat jelek.

Ayo kita coba rekursi.

Seperti yang bisa kita lihat, ketika fungsi mendapatkan departemen untuk dijumlahkan, disana terdapat dua kemungkinan:

  1. Antara itu adalah sebuah departemen ???simpel??? dengan sebuah array dari orang ??? lalu kita bisa menjumlahkan gajinya dengan perulangan yang sederhana.
  2. Atau itu adalah sebuah objek dengan N sub-departemen ??? maka kita bisa membuat pemanggilan rekursif N untuk mendapatkan jumlah untuk setiap sub-departemen dan menjumlahkan hasilnya.

Dalam kasus pertama adalah dasar dari rekursi, kasus biasa, ketika kita mendapatkan sebuah array.

Kasus kedua ketika kita mendapatkan sebuah objek adalah langkah rekursif. Sebuah task yang kompleks dibagi menjadi sub-task untuk departemen yang lebih kecil. Mereka mungkin nanti akan terbagi lagi, tapi cepat atau lambat pembagiannya akan selesai pada (1).

x Algoritmanya mungkin lebih mudah untuk dibaca dari kodenya:

let company = { // objek yang sama, dikompresi untuk keringkasan
  sales: [{name: 'John', salary: 1000}, {name: 'Alice', salary: 1600 }],
  development: {
    sites: [{name: 'Peter', salary: 2000}, {name: 'Alex', salary: 1800 }],
    internals: [{name: 'Jack', salary: 1300}]
  }
};

// Fungsinya melakukan pekerjaannya
function sumSalaries(department) {
  if (Array.isArray(department)) { // kasus (1)
    return department.reduce((prev, current) => prev + current.salary, 0); // jumlahkan arraynya
  } else { // kasus (2)
    let sum = 0;
    for (let subdep of Object.values(department)) {
      sum += sumSalaries(subdep); // secara rekursif memanggil sub-departemen, jumlahkan hasilnya
    }
    return sum;
  }
}

alert(sumSalaries(company)); // 7700

Kodenya pendek dan mudah untuk dimengerti (semoga?). Itulah kemampuan dari rekursi. Itu juga bekerja untuk level apapun dari sub-departemen bercabang.

Ini adalah diagram dari pemanggilannya:

Kita bisa dengan mudah melihat prinsipnya: untuk sebuah objek sub-pemanggilan {...} dibuat, semerata array [...] adalah daun dari pohon rekursi, mereka memberikan hasil secara langsung.

Ingat bahwa kodenya menggunakan fitur pintar yang sudah kita bahas sebelumnya:

  • Metode arr.reduce menjelaskan didalam bab Metode *array* untuk mendapatkan jumlah dari array.
  • Perulangan for(val of Object.values(obj)) untuk mengiterasi nilai didalam objek: Object.values mengembalikan sebuah array darinya.

Struktur rekursif

Sebuah struktur data rekursif (ditetapkan secara rekursif) adalah sebuah struktur yang mengulangi dirinya-sendiri dalam beberapa bagian.

Kita juga telah melihatnya didalam contoh struktur perusahaan diatas.

Sebuah departemen perusahaan adalah:

  • Diantara sebuah array dari orang-orang
  • Atau sebuah objek dengan departemen.

Untuk seorang pengembang-web disana terdapat contoh yang lebih baik: HTML dan dokumen XML.

Didalam dokumen HTML, sebuah tag-HTML mungkin mengandung daftar dari:

  • Potongan-potongan text.
  • Komentar-komentar HTML.
  • Tag-HTML Lainnya (itu mungkin saja mengandung potongan text/komentar atau tag lainnya).

Itu sekali lagi adalah definisi rekursif.

Untuk pemahaman lebih baik, kita akan memperlajari satu lagi struktur rekursif bernama ???Linked list??? itu mungkin sebuah alternatif yang bagus untuk array dalam beberapa kasus.

Linked list

Bayangkan, kita ingin menyimpan sebuah daftar terstruktur didalam sebuah objek.

Pilihan naturalnya mungkin sebuah array:

let arr = [obj1, obj2, obj3];

???Tapi disana terdapat sebuah masalah dengan array. Operasi ???delete element??? dan ???insert elemen??? sangatlah mahal. Contoh, operasi arr.unshift(obj) harus memberikan nomor baru untuk membuat ruang untuk obj baru, dan jika arraynya sangat besar, itu akan memakan waktu. Sama dengan arr.shift().

Satu-satunya modifikasi struktural yang tidak membutuhkan penomoran secara besar-besaran adalah itu yang beroperasi dengan akhiran dari array: arr.push/pop. Jadi sebuah array bisa menjadi cukup lambat untuk antrian yang panjang, ketika kita harus bekerja dengan awalannya.

Alternatifnya, jika kita benar-benar membutuhkan memasukan/menghapus dengan cepat, kiat bisa memilih data struktur lainnya bernama linked list.

Element linked list didefinisikan secara rekursif sebagai sebuah objek dengan:

  • value.
  • next properti yang mereferensi elemen linked list selanjutnya atau null jika sudah mencapai akhir.

Contoh:

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

Representasi grafikal dari sebuah list:

Alternatif kode untuk pembuatan:

let list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };
list.next.next.next.next = null;

Disini kita bisa melihat lebih jelas bahwa disana terdapat beberapa objek, masing-masing memiliki value dan next mengarah ke objek disisinya. Variabel list adalah objek pertama didalam rantainya, jadi pointer next selanjutnya dari itu bisa kita dapat dari elemen apapun.

List-nya bisa dengan mudah dibagi menjadi beberapa bagian dan lalu disatukan kembali:

let secondList = list.next.next;
list.next.next = null;

Untuk menyatukan:

list.next.next = secondList;

Dan tentu saja kita bisa memasukan atau menghapus item dari manapun.

Contoh, untuk memasukan nilai baru, kita harus memperbaharui awalan dari list-nya:

let list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };

// memasukan nilai baru kedalam list-nya
list = { value: "new item", next: list };

Untuk menghapus nilai dari tengah, ganti next dengan yang sebelumnya:

list.next = list.next.next;

Kita membuat list.next melompati 1 menuju nilai 2. Nilai 1 sekarang tidak termasuk dari rentetannya. Jika itu tidak tersimpan dimanapun, itu akan secara otomatis dihapus dari memori.

Tidak seperti array, disana tidak terdapat penomoran urang secara besar-besaran, kita bisa dengan mudah menyusun kembali elemen-elemennya.

Umumnya, list tidak selalu lebih baik daripada array. Sebaliknya semua orang harusnya hanya menggunakan list.

Kekurangannya adalah kita tidak bisa dengan mudah mengakses sebuah elemen dengan nomornya. Didalam sebuah array kita bisa dengan mudah: arr[n] adalah sebuah referensi langsung. Tapi didalam list kita harus memulai dari item pertama dan maju next N kali untuk mendapatkan elemen ke Nth.

???Tapi kita tidak selalu butuh operasi seperti itu. Contoh, ketika kita membutuhkan sebuah antrian atau bahkan deque ??? struktur urutannya harus mengijinkan penambahan/penghapusan elemen dengan cepat dari kedua sisi tapi akses kedalam bagian tengah tidak dibutuhkan.

List bisa ditingkatkan:

  • Kita bisa menambahkan properti prev didalam penambahan untuk next untuk mereferensikan elemen sebelumnya, untuk berpindah mundur dengan mudah.
  • Kita juga bisa menambahkan sebuah variabel bernama tail mereferensi elemen terakhir dari list (dan memperbaharuinya ketika menambahkan/menghapus elemen dari ujung terakhir).
  • Struktur data mungkin bervariasi tergantung dari kebutuhan kita.

Rangkuman

Istilah:

  • Rekursi adalah sebuah istilah programming yang berarti memanggil fungsi dari dirinya sendiri. Fungsi rekursi bisa digunakan untuk memecahkan tugas dengan cara yang elegan.

    Ketika sebuah fungsi memanggil dirinya sendiri, itulah yang disebut dengan langkah rekursi. Dasar dari rekursi adalah sebuah argumen fungsi yang membuat task menjadi lebih sederhana yang dimana fungsinya tidak membuat pemanggilan lebih jauh.

  • Sebuah struktur data didefinisikan secara rekursif adalah struktur data yang bisa mendefinisikan menggunakan dirinya sendiri.

    Contoh, linked list bisa didefinisikan sebagai sebuah struktur data yang terdiri dari sebuah objek yang mereferensi sebuah list (atau null).

    list = { value, next -> list }

    Pohon seperti pohon elemen HTML atau pohon departemen dari bab ini juga secara natural rekursif: cabang mereka dan setuap cabang mempunyai cabang lainnya.

    Fungsi rekursif bisa digunakan untuk menyusurinya seperti yang telah kita lihat didalam contoh sumSalary.

Fungsi rekursif manapun bisa ditulis ulang menggunakan iterasi. Dan itu terkadang membutuhkan hal-hal optimasi. Tapi untuk kebanyakan task sebuah solusi rekursif cukup cepat dan mudah untuk ditulis dan didukung.

Tugas

Tulis sebuah fungsi sumTo(n) yang mengkalkulasikan penambahan dari angka 1 + 2 + ... + n.

Contoh:

sumTo(1) = 1
sumTo(2) = 2 + 1 = 3
sumTo(3) = 3 + 2 + 1 = 6
sumTo(4) = 4 + 3 + 2 + 1 = 10
...
sumTo(100) = 100 + 99 + ... + 2 + 1 = 5050

Buatlah jawaban dengan 3 varian:

  1. Gunakan perulangan
  2. Gunakan rekursi, karena sumTo(n) = n + sumTo(n-1) untuk n > 1.
  3. Gunakan rumus arithmetic progression.

Contoh dari hasil:

function sumTo(n) { /*... kodemu ... */ }

alert( sumTo(100) ); // 5050

Catatan. Varian solusi mana yang lebih cepat? yang lebih lambat? kenapa?

Catatan+. Bisakah kita gunakan rekursi untuk menghitung sumTo(100000)?

Solusi menggunakan perulangan:

function sumTo(n) {
  let sum = 0;
  for (let i = 1; i <= n; i++) {
    sum += i;
  }
  return sum;
}

alert( sumTo(100) );

Solusi menggunakan rekursi:

function sumTo(n) {
  if (n == 1) return 1;
  return n + sumTo(n - 1);
}

alert( sumTo(100) );

Solusi menggunakan rumus: sumTo(n) = n*(n+1)/2:

function sumTo(n) {
  return n * (n + 1) / 2;
}

alert( sumTo(100) );

Catatan. Biasanya, rumus adalah solusi tercepat. Itu hanya menggunakan 3 operasi untuk angka n apapun. Matematika mambantu!

varian perulangan adalah yang kedua dalam hal waktu. Di varian rekusif dan perulangan kita menambahkan angka yang sama. Tapi rekursi melibatkan pemanggilan bercabang dan manajemen tumpukan eksekusi. Itu juga memakan sumberdaya, jadi itu lebih lambat.

Catatan+. Beberapa mesin mendukung optimasi ???tail call???: jika sebuah pemanggilan rekursi adalah yang paling terakhir didalam fungsi (seperti dalam sumTo diatas), maka fungsi terluar tidak butuh untuk melanjutkan eksekusi, jadi mesinnya tidak akan mengingat konteks dari eksekusi. Itu akan menghilangkan beban didalam memori, jadi menghitung sumTo(100000) menjadi mungkin. Tapi jika mesin Javascript tidak mendukung optimasi tail call (kebanyakan tidak), disana akan terdapat error: ???maximum stack size exceeded???, karena disana biasanya terdapat batasan dalam total ukuran stack/penumpukan.

factorial dari sebuah angka natural adalah sebuah angka yang dikalikan dengan "angka minus satu", lalu dengan "angka minus dua", dan terus sampai 1. Faktorial dari n di notasikan sebagai n!.

Kita bisa menulis definisi dari faktorial seperti ini:

n! = n * (n - 1) * (n - 2) * ...*1

Nilai dari faktorial untuk n yang berbeda:

1! = 1
2! = 2 * 1 = 2
3! = 3 * 2 * 1 = 6
4! = 4 * 3 * 2 * 1 = 24
5! = 5 * 4 * 3 * 2 * 1 = 120

Tugasnya adalah untuk menulis sebuah fungsi factorial(n) yang mengkalkulasikan n! menggunakan pemanggilan rekursi.

alert( factorial(5) ); // 120

Catatan. Petunjuk: n! bisa juga ditulis sebagai n * (n-1)!, Contoh: 3! = 3*2! = 3*2*1! = 6

Secara definisi, sebuah faktorial adalah n! bisa ditulis juga sebagai n * (n-1).

Dengan kata lain, hasil dari factorial(n) bisa juga dikalkulasikan sebagai n dikalikan dengan hasil dari factorial(n-1). Dan pemanggilan untuk n-1 bisa secara rekursi menurun, dan terus menurun sampai 1.

function factorial(n) {
  return (n != 1) ? n * factorial(n - 1) : 1;
}

alert( factorial(5) ); // 120

Basis dari rekursi adalah nilai 1. Kita jika bisa membuat basis 0 disini, tidak akan berpengaruh banyak, tapi memberikan satu lagi tingkat rekursi:

function factorial(n) {
  return n ? n * factorial(n - 1) : 1;
}

alert( factorial(5) ); // 120

Urutan dari Fibonacci numbers mempunyai rumus Fn = Fn-1 + Fn-2. Dengan kata lain, angka selanjutnya adalah penambahan dari dua angka sebelumnya.

Dua angka pertama adalah 1, lalu 2(1+1), lalu 3(1+2), 5(2+3) dan seterusnya: 1, 1, 2, 3, 5, 8, 13, 21....

Angka fibonnaci adalah angka yang terkait kedalam Golden ratio dan fenomena natural lainnya disekitar kita.

Buat sebuah fungsi fib(n) yang mengembalikan angka fibonacci ke-n-th.

Contoh hasil:

function fib(n) { /* kodemu */ }

alert(fib(3)); // 2
alert(fib(7)); // 13
alert(fib(77)); // 5527939700884757

Catatan. Fungsinya haruslah cepat. Pemanggilan ke fib(77) haruslah tidak memakan lebih dari beberapa detik.

Solusi pertama kita harus coba adalah rekursi.

Angka fibonacci adalah rekursi dari definisinya:

function fib(n) {
  return n <= 1 ? n : fib(n - 1) + fib(n - 2);
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
// fib(77); // akan sangat lambat!

???Tapi untuk nilai besar dari n akanlah sangat lambat. Contoh, fib(77) mungkin akan memberatkan mesinnya dan untuk beberapa saat akan menggunakan seluruh sumberdaya CPU.

Itu karena fungsinya memanggil terlalu banyak pemanggilan. Nilai yang sama akan terus di evaluasi lagi dan lagi.

Contoh, kita lihat satu potongan dari kalkulasi untuk fib(5):

...
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
...

Disini kita bisa melihat nilai dari fib(3) dibutuhkan untuk fib(5) dan fib(4). Jadi fib(3) akan dipanggil dan dievaluasi dua kali secara bergantian.

Ini adalah pohon rekursi penuh:

Kita dengan jelas bisa memperhatikan bahwa fib(3) dievaluasi dua kali dan fib(2) di evaluasi tiga kali. Total dari komputasi akan terus membesar secara cepat lebih dari n, membuatnya besar sekali bahkan untuk n=77.

Kita bisa mengoptimasinya dengan mengingat nilai yang telah dievaluasi: jika sebuah nilai katakan fib(3) dikalkulasi sekali, lalu kita bisa menggunakan nilainya lagi di komputasi selanjutnya.

Varian lainnya haruslah menyerah dengan rekursi dan menggunakan algoritma lain yang benar-benar berbeda.

Daripada memulai dari n ke nilai yang dibawahnya, kota bisa membuat perulangan dimulai dari 1 dan 2, lalu mendapatkan fib(3) sebagai nilai penambahan mereka, lalu fib(4) sebagai nilai penambahan dua bilangan sebelumnya, lalu fib(5) dan terus naik, sampai itu mencapai nilai yang dibutuhkan. Untuk setiap langkah kita hanya membutuhkan nilai dari kedua bilangan sebelumnya.

Ini adalah detail langkah dari algoritma baru.

Mulai:

// a = fib(1), b = fib(2), nilai-nilai ini adalah definisi dari 1
let a = 1, b = 1;

// get c = fib(3) sebagai penambahan mereka
let c = a + b;

/* sekarang kita punya fib(1), fib(2), fib(3)
a  b  c
1, 1, 2
*/

sekarang kita ingin mendapatkan fib(4) = fib(2) + fib(3).

Lalu kita ubah variabelnya: a,b akan mendapatkan fib(2),fib(3), dan c akan mendapatkan penambahan mereka:

a = b; // now a = fib(2)
b = c; // now b = fib(3)
c = a + b; // c = fib(4)

/* sekarang kita punya urutannya:
   a  b  c
1, 1, 2, 3
*/

Langkah selanjutnya akan memberikan urutan angka lainnya:

a = b; // now a = fib(3)
b = c; // now b = fib(4)
c = a + b; // c = fib(5)

/* sekarang urutannya adalah (satu angka lagi):
      a  b  c
1, 1, 2, 3, 5
*/

???Dan seterusnya sampai kita mendapatkan nilai yang dibutuhkan. Itu lebih cepat daripada rekursi dan tidak melibatkan duplikasi komputasi

Semua kodenya:

function fib(n) {
  let a = 1;
  let b = 1;
  for (let i = 3; i <= n; i++) {
    let c = a + b;
    a = b;
    b = c;
  }
  return b;
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
alert( fib(77) ); // 5527939700884757

Perulangak dimulai dari i=3, karena yang urutan nilai pertama dan kedua sudah dikode (hard-coded) kedalam variabel a=1, b=1.

Pendekatan ini dipanggil dengan dynamic programming bottom-up.

Katakan kita punya sebuah daftar single-linked (seperti yang dideskripsikan pada bab Rekursi dan tumpukan (Recursion and stack));

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

Tulis sebuah fungsi printList(list) yang mengeluarkan item dalam daftar satu per satu.

Buatlah dua varian dari solusinya: gunakan perulangan dan gunakan rekursi.

Mana yang lebih baik: dengan rekursi atau tanpa rekursi?

solusi berbasis perulangan

Varian solusi berbasis perulangan:

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

function printList(list) {
  let tmp = list;

  while (tmp) {
    alert(tmp.value);
    tmp = tmp.next;
  }

}

printList(list);

Perhatikan bahwa kita menggunakan variabel semebtara tmp untuk menyusuri daftarnya. Secara teknis, malah kita bisa menggunakan parameter fungsi list:

function printList(list) {

  while(list) {
    alert(list.value);
    list = list.next;
  }

}

???Tapi itu kurang tepat. Nanti mungkin kita ingin memperbesar fungsinya, melakukan sesuatu dengan daftarnya. Jika kita merubah list, maka kita akan kehilangan kemampuannya.

Berbicara tentang nama variabel yang bagus, list disini adalah menandakan bahwa dirinya sendiri adalah list/daftar. Elemen pertama dari itu. Dan itu harus tetap seperti itu. Itu jelas dan dapat diandalkan.

Dari sisi lainnya, peran dari tmp sendiri secara eksklusif adalah daftar traversal, seperti i didalam perulangan for.

Solusi rekursif

Varian rekursif dari printList(list) mengikuti logika yang sederhana: untuk mengeluarkan sebuah daftar kita harus mengeluatkan elemen saat ini dari list, lalu lakukan hal yang sama untuk list.next:

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

function printList(list) {

  alert(list.value); // keluarkan item yang sekarang

  if (list.next) {
    printList(list.next); // lakukan hal yang sama dengan sisa item dalam list
  }

}

printList(list);

Sekarang mana yang lebih baik?

Secara teknis, perulanganlah yang lebih efektif. Kedua varian itu melakukan hal yang sama, tapi perulangan tidak menghabiskan sumberdaya untuk pemanggilan fungsi yang bercabang.

Disisi lainnya, varian rekursi lebih pendek dan terkadang lebih mudah untuk dimengerti.

Keluarkan item single-linked dari daftar seperti tugas sebelumnya Keluarkan sebuah daftar single-linked namun secara terbalik.

Buatlah dua solusi: menggunakan perulangan dan menggunakan rekursi.

Menggunakan rekursi

Logika rekursi sedikit lebih rumit disini.

Pertama kita harus mengeluarkan sisa item di daftarnya dan lalu mengeluarkan item yang sekarang dipilih.

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

function printReverseList(list) {

  if (list.next) {
    printReverseList(list.next);
  }

  alert(list.value);
}

printReverseList(list);

Menggunakan perulangan

Varian perulangan juga sedikit lebih rumit daripada mengeluarkannya secara langsung.

Tidak ada cara untuk mendapatkan nilai terakhir didalam list kita. Kita juga tidak bisa ???berjalan mundur???.

Jadi apa yang kita bisa lakukan adalah pertama susuri seluruh item secara langsung dan mengingat mereka didalam array, dan lalu mengeluarkan apa yang diingat dengan urutan terbalik:

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

function printReverseList(list) {
  let arr = [];
  let tmp = list;

  while (tmp) {
    arr.push(tmp.value);
    tmp = tmp.next;
  }

  for (let i = arr.length - 1; i >= 0; i--) {
    alert( arr[i] );
  }
}

printReverseList(list);

Perhatikan baik-baik bahwa solusi rekursi melakukan hal yang sama persis: itu akan menyusuri daftar, mengingat item-itemnya didalam rantai dari pemanggulan bercabang (dalam konteks penumpukan eksekusi), dan lalu mengeluarkan hasilnya.

Peta tutorial