求斐波那契数列第n个位置的值

定义

a0 = 0;
a1 = 1;
an = a(n-1)+a(n-2);

即数列：0，1，1，2，3，5，8，13，21，33，54.......

Java递归实现

public int search(int n){
    if(n<0){
        return -1;
    }else if(n == 0){
        return 0;
    }else if(n == 1){
        return 1;
    }else{
        return search(n-1)+search(n-2);
    }
}

Java非递归实现

public int searchWithoutTraversal(int n){
    if(n< 0) {
        return -1;
    }
    if(n == 0||n==1){
        return n;
    }else{
        int result = 0;
        int first = 0;
        int second = 1;
        for(int i= 2;i<n;i++){
            result = first+ second;
            first = second;
            second = result;
        }
        return result;
    }
}