我正在尝试计算大量的斐波那契数列,因此我使用大整数。我最多可以达到 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;
}
}
}
最佳答案
实现您想要的系列的简单递归可能是:
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);
}
}
这当然还有其他限制,与堆栈大小无关。
关于java - 如何使用斐波那契方法实现尾递归?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46126088/