题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39

分析

斐波那契数列：

F[n] = F[n - 1] + F[n -2]

采用尾递归，防止递归时栈溢出。

贴出代码

public class Solution {
    public int Fibonacci(int n) {
        return Fibonacci(n,0,1);
    }
    
    private static int Fibonacci(int n,int acc1,int acc2){
        if(n==0) return 0;
        if(n==1) return acc2;
        else  
            return Fibonacci(n - 1, acc2, acc1 + acc2);
    }
}