So I did a dry run of the algorithm as suggested by greybeard in the comments. It turns out that for any a and n, after a certain number of recursions, one ends up getting Power(1, 2). This leads to an infinite recursion because Power(1, 2) also leads to Power (1, 2) after a certain number of recursions.
Lookup “depth first” and “breadth first” search. I’d guess you tried depth first and it fails. Try breadth first, and make sure that when a sequence can be produced in two or more ways, you ignore the second and further ways.
Here is an equivalent way to calculate $t(x,y,z)$.
We distinguish between three cases:
$x \leq z$: the answer is $y$.
$x = z + 1$: the answer is $z$ if $y \leq x$, and $x$ otherwise.
$x-z \geq 2$: the answer is $z$ (if $x-z$ is odd) or $\min(y+1,z)$ (if $x-z$ is even) if $y \leq x+1$, and $x$ (if $y-x$ is even) or $z+1$ (if $y-x$ is odd) otherwise.
Let's assume the optimal cut for 8 is: $8 = 1+2+3+2$.
When $i=3$, it means you cut at length 3, and leave 5 as a second part.
You can get the optimal value from $r_3$ and $r_5$, of course.
But please be noted, you must have already get this optimal value when $i=1$. When $i=1$, $r_8 = r_1 + r_7$, where $r_7$ can give you optimal cut as $7 = 2+3+2$.