I wanted to know if I have been tracing this recursive algorithm right:
foo(x,y) x is an integer and y a non-negative integer
if y == 0 return x
else return (foo(x, y-1))^3
for: x = 1 , y= 1. I got 1 for this one
x=2 y=3. I got 134,217,728
x=3 y=2. I got 19,683
x = 4 y= 0. I got 4.
and what output does the algorithm return for any x integer and y non negative number?. I am not sure of this question because I don't even know if I did the recursion right.
Edit:
I tried doing the proof by induction but I don't know how to work it out. This is my work so far:
Base case: when y = 0.
(foo(x,0))^3 = x^(3^0) = x^1 = x
What I assume: when y = k (any number). Assume (foo(x,k))^3 returns x^(3^k).
What I need to show: (foo(x,k+1))^3 returns x^(3^k+1). So, (foo(x,k+1))^3 returns (foo(x,k))^3, by inductive hypothesis I know it will return x^(3^k). But that does not equal to what I need to show. Am I doing this wrong?
Developing the recursion downwards, we get $$f(x,y)=f(x,y-1)^3 =f(x,y-2)^{3^2} = f(x,y-3)^{3^3} = \cdots = f(x,0)^{3^y} = x^{3^y}$$ To prove it rigorously, for fixed $x$, prove it by induction on $y$.