Recursion : pow(x,n)

• x^n = x*x*x*x.....(n times)

class Solution:
    def powiFunc(self,x:float, n:int):
        if(n==0):
            return 1

        ans = self.powiFunc(x,n-1)

        return x*ans


    def myPow(self, x: float, n: int) -> float:

       return self.powiFunc(x,n)

Recursion tree for 3^3

            powiFunc(3, 3)
               /     \
      powiFunc(3, 2)  * 3
         /     \
powiFunc(3, 1)  * 3
   /     \

powiFunc(3, 0) * 3

Now, let's evaluate the tree step by step:

1. powiFunc(3, 0) returns 1 (base case).
2. powiFunc(3, 1) returns 3 * 1 (3).
3. powiFunc(3, 2) returns 3 * (3 * 1) (9).
4. powiFunc(3, 3) returns 3 * (3 * (3 * 1)) (27).

So, 3^3 is indeed equal to 27