Fibonacci sequence

Fibonacci sequence is the most typical and relatively simple recursion , It is relatively simple to solve it with algorithmic thinking .

If you want to write an algorithm, you must first understand what Fibonacci sequence is , Fibonacci sequence （Fibonacci sequence）, also called The golden section The sequence , Leonardo the mathematician · Fibonacci （Leonardo Fibonacci） Take rabbit breeding as an example , It is also called “ Rabbit Series ”, It refers to such a sequence ：1、1、2、3、5、8、13、21、34、…… In Mathematics , The Fibonacci sequence is defined recursively as follows ：F(0)=1,F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2,n ∈ N*） In Modern Physics 、 accurate Crystal structure 、 Chemistry and so on , Fibonacci sequence has direct application , So , American Mathematics will come from 1963 Published in 《 Fibonacci series Quarterly 》 A mathematical magazine in the name of , Used to publish research results in this field .（ Source: Baidu Encyclopedia ）

Recursion is a relatively difficult Algorithm , Now I only have some ideas of my own , Recursion is difficult because it has a complex process , Nest layer after layer , I often want to give up learning recursion because it is difficult to imagine the recursive process , But giving up is easy , But persistence must be cool , Learning Fibonacci made me have some ideas about recursion .

Recursion is a nested process layer after layer , My idea is to think only about the conditions for jumping out of the process , And loops that need recursion at first , The condition for Fibonacci sequence to jump out of the cycle is when n <= 2 when , return , If it is greater than  2 when , You need the sum of the first two numbers , Notice that here is the sum of the first two numbers , Instead of the sum of all the previous numbers , Because only the first two numbers need to be considered . These two numbers are not a specific number , All you need to know is how to calculate it , The previous number can be used feiBo(n-1) Instead of , The first two numbers can be used feiBo(n-2) Instead of , So calculate a greater than 2 The number of hours , As long as you need to return feiBo(n-1) + feiBo(n-2) that will do , There is no need to think about the complex recursive process . Of course, for the standardization of the code , It is necessary to judge whether the entered value is reasonable .

The end condition of recursion is ：

if(n <= 2){
    return 1;
}else{
    return feiBo(n-1) + feiBo(n-2);
}

Add constraints and complete the construction as （ The words are not too standard ）： 

class fei{
    public int feiBo(int n){    // Back to a int type 
        if(n > 0){
            if(n <= 2){
                return 1;
            }else{
                return feiBo(n-1) + feiBo(n-2);
            }
        }else{
            return 0;
        }
    }
}

main The function and all the codes are （ In order to facilitate the constant test directly ）：

public class demo17{
	public static void main(String[] args) {
		fei b = new fei();
		int num = b.feiBo(8);
		if(num != 0){
			System.out.println(num);
		}else{
			System.out.println(" Incorrect input ！");
		}
	}
}

class fei{
	public int feiBo(int n){
		if(n>=1){
			if(n<=2){
				return 1;
			}else{
				return feiBo(n-1)+feiBo(n-2);
			}
		}else{
			return 0;
		}
	}
}

The test screenshot is ：