题目描述

输入一个整数 n ，求斐波那契数列的第 n 项。

假定从0开始，第0项为0。(n<=39)

可以采用尾递归方式

这样可以丢掉不必要的递归数据，只保留两项

C++ 代码

class Solution {
public:
    int Fibonacci(int n) {
        return Fibonacci(n, 0, 1);
    }
private:
    int Fibonacci(int n, int a, int b){
        if(n==0) return 0;
        if(n==1) return b;
        else return Fibonacci(n-1,b,a+b);
    }
};