Dynamic Programming: Fibonacci-like recurrence relation

Question

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. $$

1. Write a recursive method to compute the nth value of A, for any given integer n.
2. 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<Integer, int[]> memoizedMap = new HashMap<Integer, int[]>();

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 requested.

Actual two methods used for Bottom up algorithm:

private static int computeNthBottomUp(int n) { if (n <= 0) { throw new IllegalArgumentException("n must be an integer larger than 0"); } if (memoizedMap.containsKey(n)) { return memoizedMap.get(n)[0]; } memoizedMap.put(n, new int[]{ bottomUpHelper(n, false), bottomUpHelper(n, true) }); return memoizedMap.get(n)[0]; } // flag boolean to check if we want the B value or not private static int bottomUpHelper(int n, boolean bFlag) { if (memoizedMap.containsKey(n)) { return bFlag ? memoizedMap.get(n)[1] : memoizedMap.get(n)[0]; } memoizedMap.put(n, new int[]{ bottomUpHelper(n - 2, false) + bottomUpHelper(n - 1, true), bottomUpHelper(n - 2, true) + bottomUpHelper(n - 1, false) } ); return bFlag ? memoizedMap.get(n)[1] : memoizedMap.get(n)[0]; } 

Another convenience method:

private static String retrieveSequenceBottomUp(int begin, int end) { StringBuilder result = new StringBuilder(); for (int i = begin; i <= end; i++) { result.append(", ").append(computeNthBottomUp(i)); } return result.substring(2); } 

Sample tests:

@Test public void testTenthInSequence() { assertEquals(76, computeNthRecursive(10)); assertEquals(76, computeNthBottomUp(10)); } @Test public void testfirstTenRecursive() { assertEquals("1, 1, 3, 4, 8, 11, 21, 29, 55, 76", retrieveSequenceRecursive(10)); assertEquals("1, 1, 3, 4, 8, 11, 21, 29, 55, 76", retrieveSequenceBottomUp(1, 10)); } 

Answer 1

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; } 

Answer 2

It could be simpler. I don't read defined [] as … as to be coded using …:
$$(A_{-1} = 0, A_0 =-1), A_1 = A_2 = 1, A_3 = 3, A_4 = 4, A_n = 3A_{n-2} - A_{n-4}$$ (OEIS 1,1,3,4,8,11,21,29) If it needs spelling out:

/** next fiLuBonCasAcci fits Java long */ private static final long LIMIT = Long.MAX_VALUE / 3; /** @return nth element of http://oeis.org/A109794 */ protected static Number a(int n) { if (n <= 0) throw new IllegalArgumentException(n + " is not a natural number"); long x = (n%2) == 0 ? -1 : 0, y = 1; for (int toGo = (n+1) / 2 ; 0 < --toGo ; ) { if (LIMIT < y) // not exact. Switch to BigDecimal? throw new IllegalArgumentException("Can't be bothered to implement fiLuBonCasAcci for arguments as large as " + n); final long next = 3 * y - x; x = y; y = next; } return y; } /** @return nth element of http://oeis.org/A109794 */ protected static Number a109794(int n) { if (n <= 0) throw new IllegalArgumentException(n + " is not a natural number"); return fiLuBonCasAcci((n%2) == 0 ? -1 : 0, 1, (n-1) / 2) } /** @return toGoth element of http://oeis.org/A109794 from y */ static Number fiLuBonCasAcci(long x, long y, int toGo) { if (toGo <= 0) return y; if (LIMIT < y) { // not exact if (1 < toGo) // switch to BigDecimal? throw new IllegalArgumentException("Can't be bothered to implement fiLuBonCasAcci for values much larger than " + y); final BigDecimal Y = BigDecimal.valueOf(y); return BigDecimal.valueOf(y - x).add(Y).add(Y); } return fiLuBonCasAcci(y, 3 * y - x, --toGo); }