Nota video

Teks penuh video

Kalau kau nak kira faktorial lima, kau suruh robot panggil robot klon dia untuk tolong, klon tu panggil klon lagi, dan klon tu panggil klon lagi. Tak lama, satu kilang penuh robot yang tak buat apa-apa pun! Tapi kalau tiada arahan untuk berhenti, robot akan terus klon diri dia selama-lamanya!

Jadi, kau letak satu syarat mudah: kalau nombor dah sampai satu, terus jawab satu dan jangan panggil sesiapa lagi. Ini namanya base case. Tapi bila robot klon pulang dengan jawapan, robot asal dah lupa dia tengah buat kerja apa!

Jadi, setiap kali fungsi dipanggil, komputer letak satu plat el i ji o berisi nombor dan tempat untuk sambung kerja, bertindan atas plat sebelumnya, dan plat paling atas diangkat dulu bila selesai. Ini namanya call stack. Tapi kalau robot hantar nombor yang sama kepada klon, masalah tak pernah mengecil dan base case tak akan sampai!

Jadi, setiap panggilan mesti hantar versi lebih kecil, contohnya lima darab faktorial empat, kemudian empat darab faktorial tiga, sampai jumpa satu. Ini namanya recursive case. Tapi ruang memori untuk call stack terhad, jadi kalau rekursi terlalu dalam, menara plat tembus siling dan program crash dengan ralat stack overflow!

Jadi, untuk data yang sangat besar, kau tukar rekursi kepada gelung biasa yang guna satu plat sahaja dan kemas kini nilai berulang kali. Ini namanya iterasi. Tapi untuk Fibonacci, robot kira nombor yang sama beratus kali dan kilang membazir tenaga!

Jadi, setiap jawapan yang dah siap kau simpan dalam rak, dan robot semak rak dulu sebelum panggil klon baharu. Ini namanya memoization. Ringkasnya, rekursi ialah fungsi yang panggil diri sendiri dengan masalah lebih kecil, berhenti di base case, dan setiap panggilan disimpan dalam call stack.

Kalau terlalu dalam, stack penuh dan berlakulah stack overflow. Lepas ni nak belajar apa pula?

Siri Teknologi dan AI dalam animasi 3D LEGO (V916-030) oleh KongsikanDotCom. Tonton lagi di