Hướng dẫn tìm hiểu Fibonaci

Đệ quy có nhớ & Đệ quy không nhớ

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package aptech;

import java.util.Scanner;

/**
 *
 * @author Diep.Tran
 */
public class FibonaciTest {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        System.out.println("Nhap vi tri N can tim so Fibonaci: ");
        int N = scan.nextInt();
        
        // f0 => n - 2
        // f1 => n - 1
        int f0 = 1, f1 = 1, fn = 0;
        
        // f0 = 1
        // f1 = 1
        // f2 = f0 + f1 = 2
        // f3 = f2 + f1 = 2 + 1 = 3
        //Loop
        for (int i = 2; i <= N; i++) {
            fn = f0 + f1;
            f0 = f1; //n - 2
            f1 = fn; //n - 1
        }
        System.out.println("fn : " + fn);
        
        //TEST FIB
        fn = FIB(N);
        System.out.println("FN : " + fn);
        
        //TEST de quy co nho
        int[] values = new int[N + 1];
        values[0] = 1;
        values[1] = 1;
        fn = FIB2(N, values);
        System.out.println("FN : " + fn);
    }
    
    static int FIB(int n) {
        if(n == 0 || n == 1) {
            return 1;
        }
        return FIB(n - 1) + FIB(n - 2);
    }
    
    static int FIB2(int n, int[] values) {
        if(values[n] > 0) {
            return values[n];
        }
        values[n] = FIB2(n - 1, values) + FIB2(n - 2, values);
        return values[n];
    }
}