使用递归从用户输入确定斐波纳契数

Question

• 从我的作业中，我需要让用户输入数字形式的数字，并将其转换为序列中的同时斐波那契数，同时使用递归。
• 我的问题是如何通过数组生成序列但不存储它，因此数组可以是用户输入的数字的大小...这是我的一些起始代码：

  import java.util.Scanner;
  
  public class ReverseUserInput1 {
      //a recursive method to reverse the order of user input
      public static void main(String[] args) {
          Scanner in = new Scanner(System.in);   
          ReverseUserInput1 reverseIt = new ReverseUserInput1();    //creates new object
  
          System.out.print("Program to convert a number to a fibonacci number,");
          System.out.print("  - press Enter after each number.  ");
          System.out.println("- type \'0 or 1\' to finish the program.");
          System.out.print(" --Enter a number: ");
          int aNum = in.nextInt();
  
          reverseIt.reverseInput(aNum); //invokes reverseInput() method
      }
  
      public static int reverseInput() {
          if(aNum == 0) {
              return aNum;
          }
          else if(aNum == 1) {
              return aNum;
          }     
          else {
              reverseInput();
          }
  
          System.out.println(aNum);       
      }
  }

Answer 1

这是一种方法，请注意this还包括negafibonacci序列;

private static Map<Integer, BigInteger> fibCache = 
    new HashMap<Integer, BigInteger>();

public static BigInteger fib(int n) {
    // Uses the following identities, fib(0) = 0, fib(1) = 1 and fib(2) = 1
    // All other values are calculated through recursion.
    if (n > 0) {
        // fib(1) and fib(2)
        if (n == 1 || n == 2) {
            return BigInteger.ONE;
        }
        synchronized (fibCache) {
            if (fibCache.containsKey(n)) {
                return fibCache.get(n);
            }
            BigInteger ret = fib(n - 2).add(fib(n - 1));
            fibCache.put(n, ret);
            return ret;
        }
    } else if (n == 0) {
        // fib(0)
        return BigInteger.ZERO;
    }
    if (n % 2 == 0) {
        return fib(-n).multiply(BigInteger.ZERO.subtract(BigInteger.ONE));
    }
    return fib(-n);
}

public static void main(String[] args) throws Exception {
    for (int x = -8; x <= 8; x++) {
        System.out.println(fib(x));
    }
}

输出

-21
13
-8
5
-3
2
-1
1
0
1
1
2
3
5
8
13
21

Answer 2

我不打算发布实际算法（请参阅我之前对他的问题的评论），但后来我发现了一个不必要的复杂版本。相反，我将发布简洁的实现。注意，这个返回以1,1,2开头的序列。另一个变体以0,1,1,2开头，但在其他方面是等效的。该函数假定输入值为1或更高。

int fib(int n) {
    if(n == 1 || n == 2) return 1;
    return fib(n-2) + fib(n-1);
}

就这样。