我正在尝试制作一个不使用Java中递归的斐波那契数计算器。但是，当我运行程序时，它会生成一个无限的循环。我已经提出了许多打印声明来尝试调试它，但老实说，我什至不太确定堆栈应该如何工作。这是我的两个课程：
package fibNumbers.fibStack;
import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
/**
* A utility class containing methods to compute Fibonacci numbers.
*
* @author EECS2030 Fall 2016-17
*
*/
public class Fibonacci {
private Fibonacci() {
// empty by design
}
private static Map<Integer, BigInteger> cache = new HashMap<Integer, BigInteger>();
/**
* Memoized recursive implementation for computing Fibonacci numbers.
* This method will fail for modest values of n because of limits
* on the size of the call stack memory.
*
* @param n which Fibonacci number to compute
* @return the value of F(n)
*/
public static BigInteger fib(int n) {
BigInteger sum = null;
if (n == 0) {
sum = BigInteger.ZERO;
}
else if (n == 1) {
sum = BigInteger.ONE;
}
else if (cache.containsKey(n)) {
sum = cache.get(n);
}
else {
BigInteger fMinus1 = Fibonacci.fib(n - 1);
BigInteger fMinus2 = Fibonacci.fib(n - 2);
sum = fMinus1.add(fMinus2);
cache.put(n, sum);
}
return sum;
}
/**
* Memoized iterative implementation for computing Fibonacci numbers
* using an explicit call stack and simulated stack frames.
*
* @param n which Fibonacci number to compute
* @return the value of F(n)
*/
public static BigInteger fib2(int n) {
Stack<FibonacciStackFrame> callStack = new Stack<FibonacciStackFrame>();
FibonacciStackFrame f = new FibonacciStackFrame(n, null);
callStack.push(f);
while (!callStack.isEmpty()) {
f = callStack.peek();
f.execute(callStack);
System.out.println("Finished execution, starting loop again.");
}
return f.getReturnValue();
}
public static void main(String[] args) {
System.out.println("F(10000) = " + Fibonacci.fib2(10000));
}
}
和我的堆栈框架类。迭代运行30次之后，我不例外，因为它永远不会停止。
package fibNumbers.fibStack;
import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
/**
* A stack frame for computing Fibonacci numbers.
*
* @author EECS2030 Fall 2016-17
*
*/
public class FibonacciStackFrame {
private static Map<Integer, BigInteger> cache = new HashMap<Integer, BigInteger>();
private int n;
private FibonacciStackFrame caller;
private boolean fMinus1Computed;
private boolean fMinus2Computed;
private BigInteger fMinus1;
private BigInteger fMinus2;
private BigInteger sum;
public static int timesExecuted = 0;
/**
* Creates a stack frame to compute F(n). <code>caller</code> is a reference
* to the <code>FibonacciStackFrame</code> that created this stack frame. If
* this stack frame is not being created by another
* <code>FibonacciStackFrame</code> instance, then <code>caller</code> is
* expected to be equal to <code>null</code>.
*
*
* @param n
* the Fibonccci number to compute
* @param caller
* the <code>FibonacciStackFrame</code> that created this stack
* frame
* @throws IllegalArgumentException
* if n is less than 0
*/
public FibonacciStackFrame(int n, FibonacciStackFrame caller) {
if (n < 0) {
throw new IllegalArgumentException("n must != ZERO");
}
this.n = n;
this.caller = caller;
this.fMinus1 = BigInteger.ZERO;
this.fMinus1Computed = false;
this.fMinus2 = BigInteger.ZERO;
this.fMinus2Computed = false;
this.sum = BigInteger.ZERO;
}
/**
* Receive a return value from another <code>FibonacciStackFrame</code>
* instance.
*
* <p>
* This method is used to simulate Lines 16 and 17 of the fib(int) method
* described in the lab web page. This method needs to figure out if it is
* simulating Line 16 or Line 17; continue reading for details.
* </p>
*
* <p>
* If this.fMinus1Computed is false, then this method should set
* this.fMinus1 to <code>retVal</code> (simulating Line 16), and set
* this.fMinus1Computed to true.
* </p>
*
* <p>
* If this.fMinus1Computed is true, and this.fMinus2Computed is false, then
* this method should set this.fMinus2 to <code>retVal</code> (simulating
* Line 17), and set this.fMinus2Computed to true..
* </p>
*
* <p>
* If both this.fMinus1Computed and this.fMinus2Computed are true then you
* have done something wrong elsewhere in the class, and you should throw an
* IllegalStateException.
* </p>
*
* @param retVal
* the value of F(n - 1) or F(n - 2) returned from another
* <code>FibonacciStackFrame</code> instance
* @throws IllegalStateException
* if this stack frame has already received values for both F(n
* - 1) and F(n - 2)
*/
public void receiveReturnValue(BigInteger retVal) {
System.out.println("...Now at top of this.recieveReturnValue");
if (this.fMinus1Computed == false) {
System.out.println("...Computing fMinus1, setting to true");
this.fMinus1 = retVal;
this.fMinus1Computed = true;
} else if ((this.fMinus1Computed == true) && (this.fMinus2Computed == false)) {
this.fMinus2 = retVal;
this.fMinus2Computed = true;
} else if ((this.fMinus1Computed == true) && (this.fMinus2Computed == true)) {
throw new IllegalStateException("BOTH both F(n - 1) and F(n - 2), stack frames have recieved values");
}
}
/**
* Returns the value of F(this.n) back to the caller. This simulates Line 21
* of the fib(int) method described in the lab web page.
*
* <p>
* If the caller is equal to null, then you should simply pop the call
* stack. Otherwise, you should have the caller invoke
* <code>receiveReturnValue</code> to accept the value of F(n), which can be
* obtained from the method <code>getReturnValue</code>, and then pop the
* call stack.
*
* @param callStack
* the call stack
*/
public void returnValueToCaller(Stack<FibonacciStackFrame> callStack) {
if (this.caller == null) {
System.out.println("current caller is null");
this.caller = callStack.pop();
} else {
System.out.println("Caller != null");
System.out.println("getReturnValue yields: "+this.getReturnValue());
this.receiveReturnValue(this.getReturnValue());
this.caller = callStack.pop();
System.out.println("The call stack has been popped");
}
}
/**
* Start or resume execution of this stack frame. This method is expected to
* be invoked when this stack frame is on top of the call stack. When this
* method is invoked, this stack frame can be in one of six possible states:
*
* <ol>
* <li>this stack frame is computing F(0), in which case the value 0 can be
* returned to the caller
* <li>this stack frame is computing F(1), in which case the value 1 can be
* returned to the caller
* <li>this stack frame is computing F(n) and F(n) is in the cache, in which
* case the value F(n) can be retrieved from the cache and returned to the
* caller
* <li>this stack frame is computing F(n - 1), in which case this stack
* frame should push a new stack frame onto the call stack to compute F(n -
* 1) passing <code>this</code> as the caller of the new stack frame, and
* then return from this method
* <li>this stack frame is computing F(n - 2), in which case this stack
* frame should push a new stack frame onto the call stack to compute F(n -
* 2) passing <code>this</code> as the caller of the new stack frame, and
* then return from this method
* <li>this stack frame is computing the sum F(n - 1) + F(n - 2), in which
* case this stack frame should compute the sum, put the sum in the cache,
* and return the value of the sum to the caller
* </ol>
*
* <p>
* You should write an if-else-if statement that covers the 6 cases
* described above.
* </p>
*
* @param callStack
* the call stack that this frame is on top of
*/
public void execute(Stack<FibonacciStackFrame> callStack) {
System.out.println("");
System.out.println("New Frame *** *** *** ***");
timesExecuted ++;
if(timesExecuted>20){
throw new IllegalArgumentException("***Stack overflow, infinite loop occuring***");
}
System.out.println("currentFrame.n ="+this.getN());
if (this.getN() == 0) {
timesExecuted++;
System.out.println("Execution #" + timesExecuted);
setSum(BigInteger.ZERO);
this.returnValueToCaller(callStack);
} else if (this.getN() == 1) {
System.out.println("running through case n==1");
setSum(BigInteger.ONE);
System.out.println(this.sum);
this.returnValueToCaller(callStack);
} else if (cache.containsKey(this.getN())) {
setSum(cache.get(n));
this.returnValueToCaller(callStack);
} else if (!getfMinus1Computed()) {
System.out.println("***Computing fMinus1");
System.out.println("n at this point: "+this.getN());
callStack.push(new FibonacciStackFrame(this.getN() - 1, this));
return;
} else if (!getfMinus2Computed()) {
System.out.println("*^*Computing fMinus2");
callStack.push(new FibonacciStackFrame(this.getN() - 2,this));
return;
} else {
this.setSum(fMinus1);
this.sum.add(fMinus2);
cache.put(this.getN(), this.getReturnValue());
System.out.println(cache.get(this.getN())+"End case");
this.returnValueToCaller(callStack);
}
}
// EVERYTHING BELOW THIS LINE HAS ALREADY BEEN IMPLEMENTED FOR YOU
/**
* Get the return value (F(n)) from this stack frame. The return value is
* just this.sum (which is equal to F(n-1) + F(n-2) when this frame has
* finished all of its work).
*
* <p>
* If you call this method before the frame has finished all of its work
* then you will get the wrong value for the sum.
*
* @return the value of F(n)
*/
public BigInteger getReturnValue() {
// ALREADY COMPLETED FOR YOU
return this.sum;
}
/**
* Get the cache of already computed Fibonacci numbers. This method is here
* for debugging and testing purposes.
*
* @return the cache of already computed Fibonacci numbers
*/
public static Map<Integer, BigInteger> getCache() {
return FibonacciStackFrame.cache;
}
/**
* Get the value of n. This method is here for debugging and testing
* purposes.
*
* @return the value of n
*/
public int getN() {
return this.n;
}
/**
* Get the creator of this call stack. This method is here for debugging and
* testing purposes.
*
* @return the creator of this call stack
*/
public FibonacciStackFrame getCaller() {
return this.caller;
}
/**
* Get the current value of fMinus1. This method is here for debugging and
* testing purposes.
*
* @return the current value of fMinus1
*/
public BigInteger getfMinus1() {
return this.fMinus1;
}
/**
* Get the current value of fMinus2. This method is here for debugging and
* testing purposes.
*
* @return the current value of fMinus2
*/
public BigInteger getfMinus2() {
return this.fMinus2;
}
/**
* Get the current value of fMinus1Computed. This method is here for
* debugging and testing purposes.
*
* @return the current value of fMinus1Computed
*/
public boolean getfMinus1Computed() {
return this.fMinus1Computed;
}
/**
* Get the current value of fMinus2Computed. This method is here for
* debugging and testing purposes.
*
* @return the current value of fMinus2Computed
*/
public boolean getfMinus2Computed() {
return this.fMinus2Computed;
}
/**
* Set the value of this.sum. This method is here for debugging and testing
* purposes.
*
* @param sum
* the new value for this.sum
*/
public void setSum(BigInteger sum) {
this.sum = sum;
}
}
当我进行测试时，我注意到无论我在fib2（int）中投入了什么号码，它都会陷入n在1到2之间的n值的循环中，并继续持续。我提出了很多打印语句，以便我可以找出它在做什么，依此类推，但是我认为一个主要问题是我只是不明白堆栈与缓存相关联，然后返回最终值。我还应该提到，我正在用教授给出的框架建立这些课程。
我猜这是问题：
f = callStack.peek()
窥视只是检索值，但不会从堆栈中删除它，因此堆栈永远不会空无一人。我认为您正在尝试这样做：
f = callStack.pop()
检查文档以获取更多信息
基于文档，我相信您在通话中犯了一个小错误。
/**
* Returns the value of F(this.n) back to the caller. This simulates Line 21
* of the fib(int) method described in the lab web page.
*
* <p>
* If the caller is equal to null, then you should simply pop the call
* stack. Otherwise, you should have the caller invoke
* <code>receiveReturnValue</code> to accept the value of F(n), which can be
* obtained from the method <code>getReturnValue</code>, and then pop the
* call stack.
*
* @param callStack
* the call stack
*/
否则，您应该让呼叫者调用
获得receiveReturnValue接受 f（n）的值，可以从方法getReturnValue...
，为了实现这一目标：
this.receiveReturnValue(this.getReturnValue());
但是该方法的文档说：
从另一个
FibonacciStackFrame接收返回值 实例。（强调我的）
您正在在this帧上调用它。我看不到您实际将值返回到任何呼叫者的位置。我认为应该是：
caller.receiveReturnValue(this.getReturnValue());