如何使用我的Fibonacci方法实现Tail递归？

我正在尝试计算大量的Fibonacci序列，因此我使用大整数。 我的方式可以达到10000左右，但是我的堆栈空间不足。 我意识到我可以增加堆栈和堆空间，但我的理解是尾递归可以解决空间问题。 这是我的代码..

public class FibRecursion{ static BigInteger[] fval; public static void main(String[] args) { int index; Scanner input = new Scanner(System.in); index = input.nextInt(); fval = new BigInteger[index + 1]; System.out.println(fib_rec(index)); } public static BigInteger fib_rec(int index){ BigInteger result = BigInteger.ONE; if(index <= 2){ return result; } else{ if(fval[index] != null){ result=fval[index]; } else{ result = fib_rec(index-1).add(fib_rec(index-2)); fval[index] = result; } return result; } } } 

Answer 1

一个简单的递归来实现你想要的系列可能是：

 public class FibRecursion{ private static BigInteger[] fval; public static void main(String[] args) { int index = 10; fval = new BigInteger[index]; fib(0,1,0,index); System.out.println(Arrays.toString(fval)); } public static void fib(long a, long b, int index, int endIndex ) { if (index >= endIndex) { return ; } fval[index] = BigInteger.valueOf(a).add(BigInteger.valueOf(b)); index++; fib(b, a+b, index , endIndex); } } 

为了避免堆栈限制，您可以限制递归深度并以几个“块”进行复活。 以下是一系列50个元素的示例，计算深度限制为10（ RECURRSION_DEPTH = 10 ）：

 public class FibRecursion{ private static BigInteger[] fval; //limit of the recursion depth. valid values are >=2 private final static int RECURRSION_DEPTH = 10; public static void main(String[] args) { int index = 50; fval = new BigInteger[index]; BigInteger aValue = BigInteger.valueOf(0); BigInteger bValue = BigInteger.valueOf(1); int startIndex = 0; int endIndex = RECURRSION_DEPTH; while (endIndex > startIndex) { fib(aValue,bValue,startIndex,endIndex); aValue = fval[endIndex-2]; bValue = fval[endIndex-1]; startIndex = endIndex; endIndex = Math.min(endIndex + RECURRSION_DEPTH, index); } System.out.println(Arrays.toString(fval)); } //use BigInteger to avoid integer max value limitation public static void fib(BigInteger a, BigInteger b, int index, int endIndex ) { if (index >= endIndex) { return ; } fval[index] = a.add(b); index++; fib(b, a.add(b), index , endIndex); } } 

这当然有其他限制，与堆栈大小无关。

Answer 2

这是我最喜欢的Fibonacci实现。

它是递归的，但是以O（n）运行，而不是O（2 ^ n）。

 public int fib(int n) { return recursiveFib(0, 1, n); } public int recursiveFib(int a, int b, int n) { if (n == 0) { return a; } return recursiveFib(b, a+b, n-1); } 

现在，我不确定你的尾递归必需品，或者这对你有帮助。 你也应该围绕这个逻辑做一个真正的OO实现。