Tính dãy số Fibonacci trong Java sử dụng Loop và đệ quy

Fibonacci là gì

Fibonacci là một dãy số bắt đầu bằng 2 chữ số 0 và 1, các số phía sau bằng tổng của 2 số đứng liền trước nó. Fibonacci được sử dụng nhiều trong nghiên cứu thời gian chạy của thuật toán dùng để xác định ước số chung lớn nhất của hai số nguyên. Trong số học, Wythoff array là một ma trận vô tận của các dãy số được tạo ra từ dãy số Fibonacci.

Ví dụ những số đầu tiên trong dãy Fibo: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Fibonacci – sử dụng for loop

Theo mô tả về tính chất của dãy số fibonacci, chúng ta sẽ có 2 số khởi đầu của dãy là 0 và 1. Sử dụng vòng lặp chúng ta có thể cộng dồn 2 số trước đó để tìm ra số tiếp theo trong dãy. Lưu ý trong ý dụ này chúng ta sẽ nhận và một số maxNumber chỉ định maxNumber số đầu tiên trong dãy fibo được xuất ra  Ví dụ maxNumber = 10 tất là chúng ta sẽ xuất ra 10 chữ số đầu tiên trong dãy fibo.

public class Main {

    public static void main(String[] args) {
        fibonacci(10);
    }

    public static void fibonacci(int maxNumber) {
        int previousNumber = 0;
        int nextNumber = 1;
        System.out.print("Fibonacci Series of " + maxNumber + " numbers:");
        for (int i = 1; i <= maxNumber; ++i) {
            System.out.print(previousNumber + " ");
            int sum = previousNumber + nextNumber;
            previousNumber = nextNumber;
            nextNumber = sum;
        }
    }
}

Output

Fibonacci Series of 10 numbers:0 1 1 2 3 5 8 13 21 34 

Fibonacci – sử dụng While loop

Tương tự chúng ta có thể sử dụng while thay thế cho for trong trường hợp bắt buộc sử dụng hoặc theo yêu cầu cụ thể.

public class Main {

    public static void main(String[] args) {
        fibonacci(10);
    }

    public static void fibonacci(int maxNumber) {
        int previousNumber = 0, nextNumber = 1;
        System.out.print("Fibonacci Series of " + maxNumber + " numbers:");

        int i = 1;
        while (i <= maxNumber) {
            System.out.print(previousNumber + " ");
            int sum = previousNumber + nextNumber;
            previousNumber = nextNumber;
            nextNumber = sum;
            i++;
        }
    }
}

Output

Fibonacci Series of 10 numbers:0 1 1 2 3 5 8 13 21 34

Fibonacci – đệ quy

Đệ quy là một hàm có khả năng gọi lại chính nó, để áp dụng đệ quy để tính dãy số fibonacci chúng ta cần thực hiện các bước sau:

• Nhận vào một số N đại diện cho số thứ N trong dãy fibonacci. Kiểm tra nếu N = 0, 1 thì trả về 0,1 tương ứng vì chúng là các chữ số bắt đầu của dãy số fibo. Đây cũng được xem là điều kiện dừng trong quy tắc viết một hàm đệ quy.
• Nếu N >= 3,  hàm đệ quy sẽ gọi lại chính nó với N – 1 và N – 2, do vậy kết quả số fibo thứ N được tính từ số fibo N – 1 và N – 2.

Gỉa sử dụng N = 4 chúng ta sẽ có các bước sau:

fibonacciRecursion(4)
- fibonacciRecursion sẽ gọi đệ quy lại chính nó với fibonacciRecursion(3) và fibonacciRecursion(2)
  -> fibonacciRecursion(2) gọi đệ quy chính nó với  fibonacciRecursion(1) = 1 + fibonacciRecursion(0) = 0 => kết quả = 1 (A)
  -> fibonacciRecursion(3) gọi đệ quy chính nó với  fibonacciRecursion(2)(*) + fibonacciRecursion(1) = 0 (B)
     -> fibonacciRecursion(2) gọi đệ quy chính nó với  fibonacciRecursion(1) = 1 + fibonacciRecursion(0) = 0 => kết quả = 1 (C)
Kết quả cuối cùng (A) + (B) + (C) = 2

public class Main {
    public static int fibonacciRecursion(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        return fibonacciRecursion(n - 2) + fibonacciRecursion(n - 1);
    }

    public static void main(String args[]) {
        int maxNumber = 10;
        System.out.print("Fibonacci Series of " + maxNumber + " numbers: ");
        for (int i = 0; i < maxNumber; i++) {
            System.out.print(fibonacciRecursion(i) + " ");
        }
    }
}

Output

Fibonacci Series of 10 numbers: 0 1 1 2 3 5 8 13 21 34