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

不念不忘少年蓝@ 2022-12-17 15:52 108阅读 0赞

![在这里插入图片描述][20201024112353367.png_pic_center]  
裴波那契数列的规律就是第0项为0，第一项为1，从第2项开始后一个等于前两个之和  
![在这里插入图片描述][20201024114034652.png_pic_center]  
利用数学规律递归

public class Solution {
        
        public int Fibonacci(int n) {
        
            if(n == 0){
        
                return 0;
            }
            if(n == 1){
        
                return 1;
            }else{
        
            return (Fibonacci(n-1)+Fibonacci(n-2));            
            }
    
        }
    }

非递归迭代版本

public class Solution {
        
        public int Fibonacci(int n) {
        
            if(n == 0){
        
                return 0;
            }
            if(n == 1){
        
                return 1;
            }
            int a = 0;
            int b = 1;
            int c = 0;
            for(int i = 2; i <= n; i++){
        
                c = a + b;
                a = b;
                b = c;
            }
            return c;
    
        }
    }

[20201024112353367.png_pic_center]: /images/20221122/ea19b30714bb45958d1d21be86957ac2.png
[20201024114034652.png_pic_center]: /images/20221122/a2220b15851947dc9cc95ab29a7660f3.png