A recursive program that attempts to solve an extremely large number
Your function is extremely slow because it does a lot of redundant calculations.

$$
\begin{align}
G(5) =&amp; (G(4) + G(3))^{2} \\
     =&amp; (G(4) + G(3)) \cdot (G(4) + G(3)) \\
     =&amp; ((G(3) + G(2))^{2} + (G(2) + G(1))^{2})) \cdot ((G(3) + G(2))^{2} + (G(2) + G(1))^{2})) \\
     =&amp; ((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))))) \\
     =&amp; \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) =&amp; (G(4) + G(3))^{2} \\
     =&amp; ((G(3) + G(2))^{2} + (G(2) + G(1))^{2}))^{2} \\
     =&amp; \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.