Thuật toán C/C++

Đệ quy và call stack

Mọi recursive function cần base case và tiến dần về nó.

Đệ quy và call stack là gì?

Mọi recursive function cần base case và tiến dần về nó.

Giải bài toán bằng instance nhỏ hơn.

Điểm quan trọng

Test input rỗng, một phần tử, trùng lặp và đã sắp xếp.
Tách correctness khỏi optimization.
Ưu tiên standard library trong code production.

Code ví dụ bằng C và C++

Chạy code →

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));
}

Output dự kiến

C++

Chạy code →

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';
}

Output dự kiến

So sánh C và C++

Factorial dùng O(n) thời gian và O(n) call-stack; input lớn cần validation và thường nên dùng iterative solution.

Loop, pointer, length và buffer tạm được viết tường minh.

C++

Iterator và standard algorithm tách operation khỏi cách lưu dữ liệu.

Bài tập mở rộng

Chạy cả hai phiên bản rồi thay đổi để quan sát khác biệt về bảo đảm của từng ngôn ngữ.

Trace từng phép so sánh trên giấy.
Test duplicate và extreme value.
Benchmark code tự viết với standard library.