Recursion และ Call Stack
Recursive function ต้องมี base case และเคลื่อนไปหา base case
Recursion และ Call Stack คืออะไร?
Recursive function ต้องมี base case และเคลื่อนไปหา base case
แก้ปัญหาด้วย instance ที่เล็กลง
ประเด็นสำคัญ
- ทดสอบ input ว่าง หนึ่งสมาชิก ซ้ำ และเรียงแล้ว
- แยก correctness จาก optimization
- ใช้ standard library ใน production เมื่อเหมาะสม
ตัวอย่างโค้ด C และ C++
main.c
#include <stdio.h>
unsigned long long factorial(unsigned number) {
return number < 2 ? 1 : number * factorial(number - 1);
}
int main(void) {
printf("%llu\n", factorial(6));
}
720C++
main.cpp
#include <iostream>
constexpr unsigned long long factorial(unsigned number) {
return number < 2 ? 1 : number * factorial(number - 1);
}
int main() {
constexpr auto value = factorial(6);
std::cout << value << '\n';
}
720เปรียบเทียบ C และ C++
Factorial ใช้เวลา O(n) และ stack O(n) input ใหญ่ควร validate และพิจารณา iterative solution
C
Loop, pointer, length และ buffer เขียนอย่างชัดเจน
C++
Iterator และ algorithm แยก operation จาก storage
แบบฝึกหัด
รันทั้งสองเวอร์ชันแล้วแก้ไขเพื่อสังเกตความแตกต่างของภาษา
- ไล่ตามทุก comparison
- ทดสอบ duplicate และ extreme value
- Benchmark กับ standard library