Dynamic Programming: Fibonacci-like recurrence relation

This is a problem from my Introduction to Algorithms textbook.


Consider the infinite sequence of numbers An|n>0 = (1,1,3,4,8,11,...) defined recursively as follows.

$$
A_n = \left\{\begin{aligned}
&1 && n = 1,2\\
&B_{n-1}+A_{n-2} && n > 2
\end{aligned}
\right. \\
B_n = \left\{\begin{aligned}
&2 && n = 1,2\\
&A_{n-1}+B_{n-2} && n > 2
\end{aligned}
\right.
$$

• Write a recursive method to compute the nth value of A, for any given integer n.

• Write a “bottom-up” method to compute the nth value of A, for any given integer n.

I wrote a solution for each but found myself using auxiliary methods in both cases. A recent criticism comes to mind and I wonder if this is unnecessarily complex. Could it be simpler?

Of course any feedback on the efficacy of my approach is welcomed.

My recursive algorithm, stratified into two methods:

private static int computeAuxRecursive(int n) {
  if (n <= 0) {
    throw new IllegalArgumentException("n mustbe an integer larger than 0");
  }
  return n <= 2 ? 2 : computeNthRecursive(n - 1) + computeAuxRecursive(n - 2);
}

private static int computeNthRecursive(int n) {
 if (n <= 0) {
   throw new IllegalArgumentException("n must be an integer larger than 0");
 }
  return n <= 2 ? 1 : computeAuxRecursive(n - 1) + computeNthRecursive(n - 2);
}

Convenient testing method:

private static String retrieveSequenceRecursive(int length) {
    StringBuilder result = new StringBuilder();
    for (int i = 1; i <= length; i++) {
        result.append(", ").append(computeNthRecursive(i));
    }
    return result.substring(2);
}

For my bottom-up algorithm I elected to go with a map:

private static Map memoizedMap = new HashMap();

Pre-filled, according to specification, like so:

memoizedMap.put(1, new int[]{1, 2});
memoizedMap.put(2, new int[]{1, 2});

The idea is to use the Nth position requested as a key, and the array of length 2 to hold both the A and B value, using a flag to determine which is being re

Recursive Solution

Code-wise, I see no issues. The one thing I'd point out is that it might be clearer to name your functions A and B instead of Nth and Aux, since the problem has to do with finding A and it isn't readily apparent what Aux means. It's a little unclear, but not a dealbreaker.

Bottom-up method

I don't really understand why your memoized map contains an array. If it's really a "pair" type such that memoizedMap[n] is \$(A_n, B_n)\$, then I'd introduce a new type for that. Arrays can mean anything, so once you make the decision to go with an array, the code is very difficult to follow. You're introducing some boolean flags, which are probably unnecessary too.

That said, I'm not sure that simply memoizing the recursive solution is what the problem intended. The intent seems to instead suggest that you compute the arrays iteratively. That is just the same way you could compute the Fibonacci sequence iteratively (in fact, the two sequences are very closely related, as \$A_1, B_2, A_3, B_4, ...\$ is the Fibonacci sequence): just keep the last few elements and update them as you go:

public static int getAn(int n) {
    if (n <= 2) return 1;

    int a0 = 1;
    int a1 = 1;
    int b0 = 2;
    int b1 = 2;

    for (int i = 0; i < n-2; ++i) {
        int nexta = b1 + a0;
        int nextb = a1 + b0;

        // updates
        a0 = a1;
        a1 = nexta;
        b0 = b1;
        b1 = nextb;
    }

    return a1;
}

StackExchange Code Review Q#114902, answer score: 10