javarecursionfibonacciladder-logic

ladder, 1 or 2 rungs at a time, recursion / fibonacci error


I know there are a lot of already existing questions about this problem, but I haven't found anything that answers mine. My recursion is working fine for lower numbers (I tried int 10) but when I expand it to 100, it becomes exactly one step lower than it should. Not sure why.

My code:

public BigDecimal distinctLadderPaths(int rungs) {
    if (rungs < 0)
      throw new ArithmeticException("Ladders can't have negative rungs."); // if negative, throw exception
    else if (rungs == 0)
      return BigDecimal.valueOf(0); //if zero, return zero
    else if (rungs <= 2)
      return BigDecimal.valueOf(rungs); //if 1 or 2, return 1 or 2, respectively
    else{
      long[] f = new long[(rungs + 1)]; //create long Array for memory (f for fibonacci)
      f[0] = 0; //1 steps
      f[1] = 1; //2 steps
      for(int i = 2; i <= rungs; i++) { //loop
        f[i] = f[i - 1] + f[i - 2]; //at each step in the loop, add 1 step lower and 2 steps lower from the number of iterations
      }
      return BigDecimal.valueOf(f[rungs]); //return fibonacci value at final step of the rungs as BigDecimal
    }
  }

test code:

@Test
  public void testDistinctLadderPaths100 (){
    int rungs = 100;
    BigDecimal expected = new BigDecimal("573147844013817084101");
    BigDecimal result = lp.distinctLadderPaths(rungs);
    assertEquals(expected, result);
  }

I'm told the output should be 57314784401381708410, but I'm getting 3736710778780434371 (which is the fibonacci number at the 99th step). Any ideas why?


Solution

  • fibonacci seq starts from 1. Sequence is 1, 1, 2, 3, 5, 8.. so initallize f[0] = f[1] = 1;