A recursive program that attempts to solve an extremely large number

Question

This is my recursive program for the following function:

• \$F(x) = G(x) - W(x)\$
• \$G(x) = [G(x-1)+G(x-2)]^2\$
• \$W(x) = [W(x-1)]^2 + [W(x-2)]^2\$
• If x == 0 in either function G or function W, then return 0
• If x == 1 in either function G or function W, then return 1

import java.math.BigInteger;
import java.io.PrintWriter;
import java.io.IOException;

public class RecursiveProgram
{
    BigInteger test = BigInteger.valueOf(30);
    BigInteger zero = new BigInteger(Integer.toString(0));
    BigInteger one = new BigInteger(Integer.toString(1));
    BigInteger two = new BigInteger(Integer.toString(2));
    public BigInteger G(BigInteger x)
    {
        if(x.equals(zero))
            return zero;
        if(x.equals(one))
            return one;
        return (G(x.subtract(one)).add(G(x.subtract(two)))).multiply((G(x.subtract(one)).add(G(x.subtract(two)))));
    }

    public BigInteger W(BigInteger x)
    {
        if(x.equals(zero))
            return zero;
        if(x.equals(one))
            return one;
        return ((W(x.subtract(one))).multiply(W(x.subtract(one)))).add((W(x.subtract(two))).multiply(W(x.subtract(two))));
    }

    public void solveForF() throws IOException
    {
        PrintWriter writer = new PrintWriter("C:/Users/my computer/Desktop/f(30).txt");
        writer.println(G(test).subtract(W(test)));
        writer.close();
    }
}

It writes the calculated number to the .txt file on my desktop. I want to improve the recursive program to allow it to calculate F(30). However, I did some math calculations as to how long it would take for the program to complete using the amount of time it took to calculateF(20) and F(21), approximating to 12.35 days. Obviously this is inefficient and I haven't learned a better method to make it more efficient. I've heard of dynamic programming but I'm not sure as how I would use it here.

Answer 1

Your function is extremely slow because it does a lot of redundant calculations.

$$ \begin{align} G(5) =& (G(4) + G(3))^{2} \\ =& (G(4) + G(3)) \cdot (G(4) + G(3)) \\ =& ((G(3) + G(2))^{2} + (G(2) + G(1))^{2})) \cdot ((G(3) + G(2))^{2} + (G(2) + G(1))^{2})) \\ =& ((G(3) + G(2)) \cdot (G(3) + G(2)) + (G(2) + G(1)) \cdot (G(2) + G(1)))) \cdot ((G(3) + G(2)) \cdot (G(3) + G(2)) + (G(2) + G(1)) \cdot (G(2) + G(1))))) \\ =& \ldots \end{align} $$

The complexity is \$O(4^x)\$: to calculate \$G(x)\$, you're breaking it into four problems of approximately the same size.

To start with, it would be smarter to square a number without having to compute the base again.

$$ \begin{align} G(5) =& (G(4) + G(3))^{2} \\ =& ((G(3) + G(2))^{2} + (G(2) + G(1))^{2}))^{2} \\ =& \ldots \end{align} $$

Then you would be down to "just" \$O(2^x)\$, which is still horrible.

The trick is to notice that you're going to be computing \$G(2)\$, \$G(3)\$, etc. many many times. What you want to do is memoization — caching previously computed results. With memoization, you should be able to compute \$G(x)\$ in \$O(x)\$ time.

Once you solve the efficiency issue above, you will still run into a problem with stack overflow for large \$x\$. To avoid stack overflow, you'll want to reimplement the functions using an iterative loop rather than recursion.

Answer 2

This seems like a method suitable for the dynamic programming method. As 200_success said in his answer, the use of memoization can greatly improve performance. What I want to add to the answer are two ways to go with solving the problem.

In-time processing

This is the way suggested in 200_success' answer (if I understood it correctly). Let's go at it one step at a time. We have that \$G(0) = 0\$, \$G(1) = 1\$, and \$G(n) = [G(n-1) + G(n-2)]^2\$. By caching the result of \$G(n-2)\$ and \$G(n-1)\$ we can easily calculate \$G(n)\$, so, for \$n >= 2\$ we can use the following algorithm (in pseudo-code):

int calculateG(int n){
    if(n == 0){
        return 0;
    }

    if(n == 1){
        return 1;
    }

    int nMinus2 = 0;
    int nMinus1 = 1;
    int result;

    for(int i = 2; i <= n; i++){
        result = Math.pow(nMinus1 + nMinus2, 2);
        nMinus2 = nMinus1;
        nMinus1 = result;
    }

    return result;
}

This approach calculates each result in \$O(n)\$ time and has a space complexity of \$O(1)\$ and, IMO, is the way to go if the function is calculated not so often.

Cached-result processing

In case the function is calculated often I'd suggest another approach. If you use an appropriate data structure (an arraylist should be ideal) you can implement the function in the following way:

ArrayList values = new ArrayList();
// append G(0)
values.append(0);
// append G(1)
values.append(1);

int calculateG(int n){
    return getValue(n);
}

int getValue(int n){
    // this is calculated in O(n) time in the worst case (where n is greater than the current length of the list)
    for(int i = value.length - 1; i <= n; i++){
        // this is calculated in O(1) time if the get() method accesses the elements in O(1) time
        value.append(Math.pow(value.get(i) + value.get(i-1), 2));
    }

    return value.get(n);
}

This approach has a time complexity of \$O(n)\$ in the worst case (when \$n\$ is much greater than the number of cached elements) and \$O(1)\$ in the best case (when \$n\$ is smaller than, or equal to, the number of cached elements). In the average case the number of calculations is reduced, but still remains \$O(n)\$. The space complexity, on the other hand, is \$O(n)\$ in all cases.

Let me know if anything's unclear.

P.S.: The same logic applies to \$G(n)\$ and \$W(n)\$. Also, all code is pseudo-code, it's there just to better explain the idea.