This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

1. Title Description

We all know the Fibonacci sequence, and now we’re asking for an integer n, so please print the NTH term of the Fibonacci sequence (starting at 0, the 0th term is 0, and the first term is 1). (n<=39)

Second, train of thought analysis

The Fibonacci sequence is well known:

Direct violence solution, only need recursion, but direct recursion will cause a lot of repeated calculation, if we save the calculation results first, when using the call, it can be optimized.

AC code

recursive

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

non-recursive

public class Solution {
    public int Fibonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int[] nums = new int[n + 1];
        nums[0] = 0;
        nums[1] = 1;
        for (int i = 2; i <= n; i++) {
            nums[i] = nums[i - 1] + nums[i - 2];
        }
        returnnums[n]; }}Copy the code

conclusion

Recursion generally solves some iteration-related problems, or stack-related problems, because recursion is a natural stack. However, if the method call hierarchy is too deep, it can be problematic, and there can be a lot of double computation, so it is a good idea to store the result set that you need to use with the extra space.

The author has written a series of questions about the sword Offer. If you are interested, please read: 150 pages of sword Offer PDF