1. Định nghĩa chuỗi Fibonacci

Chuỗi Fibonacci, còn được gọi là dãy Fibonacci, là một chuỗi số mà trong đó mỗi số sau bằng tổng của hai số trước nó. Chuỗi này được nhà toán học người Ý Leonardo Fibonacci giới thiệu vào năm 1202. Định nghĩa chính xác của nó là:

1. Số hạng thứ nhất (F(1)) và số hạng thứ hai (F(2)) đều bằng 1;

2. Từ số hạng thứ ba trở đi, mỗi số hạng bằng tổng của hai số hạng ngay trước nó.

Công thức toán học:

F(1) = 1, F(2) = 1

F(n) = F(n-1) + F(n-2) (với n ≥ 3, n là số nguyên dương)

Dựa trên định nghĩa, 10 số hạng đầu tiên của chuỗi Fibonacci là: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...

2. Triển khai bằng phương pháp lặp

Phương pháp này sử dụng một vòng lặp để tính toán từng số hạng một, đồng thời lưu trữ hai số hạng trước đó trong các biến. Điều này giúp tránh việc tính toán lặp lại và cải thiện hiệu suất đáng kể.

#include <stdio.h>

// Hàm tính số Fibonacci thứ n bằng phương pháp lặp
int tinh_so_fibonacci(int vi_tri) {
    // Xử lý các trường hợp đặc biệt cho vị trí 1 và 2
    if (vi_tri <= 0) {
        printf("Vị trí không hợp lệ. Vui lòng nhập số nguyên dương.
");
        return -1;
    }
    if (vi_tri == 1 || vi_tri == 2) {
        return 1;
    }

    int so_truoc_truoc = 1; // Số hạng thứ 1
    int so_truoc = 1;      // Số hạng thứ 2
    int hien_tai = 0;      // Số hạng hiện tại

    // Bắt đầu vòng lặp từ vị trí thứ 3
    for (int i = 3; i <= vi_tri; ++i) {
        hien_tai = so_truoc_truoc + so_truoc;
        so_truoc_truoc = so_truoc;
        so_truoc = hien_tai;
    }
    return hien_tai;
}

int main() {
    int vi_tri = 0;
    printf("Nhập vị trí số Fibonacci cần tính: ");
    scanf("%d", &vi_tri);

    int ket_qua = tinh_so_fibonacci(vi_tri);
    if (ket_qua != -1) {
        printf("Số Fibonacci thứ %d là: %d
", vi_tri, ket_qua);
    }
    return 0;
}

3. Triển khai bằng phương pháp đệ quy

#include <stdio.h>

// Hàm tính số Fibonacci bằng đệ quy
int tinh_so_fibonacci_de_quy(int vi_tri) {
    // Xử lý đầu vào không hợp lệ
    if (vi_tri <= 0) {
        printf("Đầu vào không hợp lệ, vị trí phải là số nguyên dương!
");
        return -1;
    }
    // Điều kiện dừng đệ quy: số hạng thứ 1 và 2 đều là 1
    if (vi_tri == 1 || vi_tri == 2) {
        return 1;
    }
    // Công thức đệ quy: F(n) = F(n-1) + F(n-2)
    return tinh_so_fibonacci_de_quy(vi_tri - 1) + tinh_so_fibonacci_de_quy(vi_tri - 2);
}

int main() {
    int vi_tri = 0;
    printf("Nhập vị trí số Fibonacci cần tính: ");
    scanf("%d", &vi_tri);
    
    int ket_qua = tinh_so_fibonacci_de_quy(vi_tri);
    if (ket_qua != -1) {
        printf("Số Fibonacci thứ %d là: %d
", vi_tri, ket_qua);
    }
    return 0;
}

Ưu điểm: Mã nguồn ngắn gọn, trực quan, trực tiếp phản ánh định nghĩa toán học, dễ hiểu;

Nhược điểm: Hiệu suất rất thấp, có nhiều phép tính lặp lại (ví dụ, khi tính F(5), F(3) và F(2) sẽ được tính toán nhiều lần), khi n lớn (ví dụ n > 30) thời gian chạy sẽ tăng lên đáng kể, thậm chí gây treo chương trình.

4. Triển khai bằng đệ quy đuôi

Điều kiện tiên quyết: Đệ quy đuôi là gì?

Đệ quy đuôi là một dạng đặc biệt của đệ quy:

• Đệ quy thông thường: Bước cuối cùng của hàm là gọi chính nó + một phép toán khác (ví dụ `return fib(n-1) + fib(n-2)`), gây ra nhiều phép tính lặp lại và cần lưu trữ nhiều khung gọi.
• Đệ quy đuôi: Bước cuối cùng của hàm chỉ có lời gọi chính nó, không có phép toán bổ sung, trình biên dịch / trình thông dịch có thể tối ưu hóa thành vòng lặp (tái sử dụng khung gọi), hiệu suất gần như tương đương với phương pháp lặp.

Khóa để triển khai đệ quy đuôi: Sử dụng tham số để lưu trữ kết quả trung gian, thay vì thực hiện phép cộng sau khi lời gọi đệ quy trả về.

#include <stdio.h>

// Hàm trợ giúp cốt lõi cho đệ quy đuôi
// so_hang_1: Lưu trữ số hạng trước trước (ban đầu là số hạng 1)
// so_hang_2: Lưu trữ số hạng trước (ban đầu là số hạng 2)
// so_con_lai: Số lượng số hạng còn lại cần tính
int tro_chuyen_de_quy_duoi(int so_hang_1, int so_hang_2, int so_con_lai) {
    // Điều kiện dừng đệ quy: không còn số hạng nào cần tính, trả về số hạng hiện tại
    if (so_con_lai == 0) {
        return so_hang_1;
    }
    // Lời gọi đệ quy đuôi: chỉ cập nhật tham số, không có phép toán khác
    // so_hang_1 trở thành so_hang_2, so_hang_2 trở thành tổng của chúng, số còn lại giảm 1
    return tro_chuyen_de_quy_duoi(so_hang_2, so_hang_1 + so_hang_2, so_con_lai - 1);
}

// Hàm chính để sử dụng đệ quy đuôi (đóng gói để đơn giản hóa)
int tinh_so_fibonacci_duoi_de_quy(int vi_tri) {
    // 1. Xử lý đầu vào không hợp lệ
    if (vi_tri <= 0) {
        printf("Đầu vào không hợp lệ! Vị trí phải là số nguyên dương
");
        return -1;
    }
    // 2. Xử lý các trường hợp đặc biệt
    if (vi_tri == 1 || vi_tri == 2) {
        return 1;
    }
    // 3. Gọi hàm trợ giúp đệ quy đuôi (cấu hình tham số ban đầu)
    // Ban đầu so_hang_1=1 (số hạng 1), so_hang_2=1 (số hạng 2), còn lại tính vi_tri-2 số (vì 2 số đầu đã xác định)
    return tro_chuyen_de_quy_duoi(1, 1, vi_tri - 2);
}

// Hàm main để kiểm tra
int main() {
    int vi_tri = 0;
    printf("Nhập vị trí số Fibonacci cần tính: ");
    scanf("%d", &vi_tri);
    
    int ket_qua = tinh_so_fibonacci_duoi_de_quy(vi_tri);
    if (ket_qua != -1) {
        printf("Số Fibonacci thứ %d là: %d
", vi_tri, ket_qua);
    }
    return 0;
}