Fibonacci Stack программа в Java. Infinite loop

Question

Я пытаюсь сделать калькулятор числа фибоначчи, который не использует рекурсию в Java. Однако, когда я запускаю программу, он генерирует бесконечный цикл. Я поставил множество операторов печати, чтобы попытаться отладить его, но, честно говоря, я даже не уверен, как Stack должен работать. Вот мои два класса:

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), было бы застрять на петле значения п чередующихся между 1 и 2 и продолжать без конца. Я поставил ALOT из операторов печати, чтобы я мог проследить, что он делает и так далее, но я думаю, что основная проблема заключается в том, что я просто не понимаю, как именно стек работает в соединении с кешем, а затем возвращает окончательное значение. Я должен также упомянуть, что я строю эти классы вне рамок, данных моим профессором.

Answer 1

Я предполагаю, что эта линия является проблема:

f = callStack.peek() 

Заглянуть просто возвращает значение, но не удаляет его из стека, поэтому стек никогда не будет empty.I думаю, что вы пытаетесь сделать это :

f = callStack.pop() 

Проверить the documentation для получения дополнительной информации

Answer 2

на основе документации, которую я считаю, что вы сделали небольшую ошибку вызова.

/** 
* 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 (п), который может быть получен из метода getReturnValue ...

И для достижения этой цели вы делаете:

this.receiveReturnValue(this.getReturnValue());

Но документация для этого метода говорит:

Получить возвращаемое значение другого экземпляраFibonacciStackFrame . (акцент мой)

Вы звоните по телефону this. Я не вижу, где вы действительно возвращаете значение любому вызывающему абоненту. Я думаю, что это должно быть:

caller.receiveReturnValue(this.getReturnValue());