A recursive program that attempts to solve an extremely large number

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.

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.

StackExchange Code Review Q#112833, answer score: 4