c# - What is the workflow of Pow(x,y) function?




recursion (4)

I'm going through "sololearn" and udemy courses to try to learn C#. I am doing the challenges but could not figure out how the below code resulted with 32 (as in 32 is the correct answer here and I am trying to find out why). Can someone explain this process to me, the method calling itself is throwing me I think.

static double Pow(double x, int y)
{
    if (y == 0)
    {
        return 1.0;
    }
    else
    {
        return x * Pow(x, y - 1);
    }
}

static void Main()
{
    Console.Write(Pow(2, 5));
} 

Please excuse my bad coding. I am trying to do it on mobile, which is difficult, the answer was 32. Can someone explain why?

Edit: Aplogies here is how I work through it. Pass 2 and 5 to Pow, check if y == 0 which is false, it is now y == 5 so x * pow(x, y-1) formula will be active. X is still 2, y is now 4 which means it fails the check again on whether it equals 0, this loop continues until it returns the 1.0, x has remained at 2 so 2 * 1.0 = 2 and not 32?


First thing to note is that this is NOT how you would normally implement a power function. It's done this way to demonstrate recursion.

With that out the way, let's look at what happens when you call Pow(2, 5) :

Pow(x = 2, y = 5)
    -> return 2 * Pow(2, 4)
<- 2 * 16 = 32

  Pow(x = 2, y = 4)
      -> return 2 * Pow(2, 3)
  <- 2 * 8 = 16

    Pow(x = 2, y = 3)
        -> return 2 * Pow(2, 2)
    <- 2 * 4 = 8

      Pow(x = 2, y = 2)
          -> return 2 * Pow(2, 1)
      <- 2 * 2 = 4

        Pow(x = 2, y = 1)
            -> return 2 * Pow(2, 0)
        <- 2 * 1 = 2

          Pow(x = 2, y = 0)
              -> return 1 (because y == 0)
          <- 1

To read this representation of the recursive call stack, work your way from the top to the bottom looking at how the arguments change; then work your way back up from the bottom to the top looking at the return values (which I indicate with <- ).


Hello its recursion and it repeat until y=1 , then return 2 ,then return 4, 8, 16, 32 at then end. 2^5=32


That method basically computes " x raised to the power of y ". It does this in a recursive manner.

First, it defines a base case : anything raised to the power of 0 is 1.

Then, it defines what to do in all other cases: x * Pow(x, y - 1) . Assuming y is big, what's x * Pow(x, y - 1) ? It's x * x * Pow(x, y - 2) , which in turn is x * x * x * Pow(x, y - 3) . See the pattern here? Eventually, you will reach the point where the second argument, y - N , is 0, which as we have established, is 1. At that point, how many x * have we got? Exactly y .

Let's see this in action for Pow(2, 5) :

Pow(2, 5)
2 * Pow(2, 4)
2 * 2 * Pow(2, 3)
2 * 2 * 2 * Pow(2, 2)
2 * 2 * 2 * 2 * Pow(2, 1)
2 * 2 * 2 * 2 * 2 * Pow(2, 0)
2 * 2 * 2 * 2 * 2 * 1

Hence the result 32.


To be able to understand each action in this recursive behavior log all the details to see what is actually going on. Such as :

using System;
namespace Tester
{
    class test 
    {
        // What Pow actually does:
        static double logPow(double x, int y) {
            var old = x; // Hold the x
            for (var i = 0; i < y; i++){ // do it y times
                x = old * x; // Multiply with it's first self
            }
            return x;
        }
        static int counter = 0;
        static double Pow(double x, int y) {
            counter++;
            Console.Write("Recursive action[" + counter + "] Y status ["+ y +"] : ");
            if (y == 0)
            {
                Console.Write("return 1.0 = " + logPow(x, y) + " \n");
                return 1.0;
            }
            else
            {
                Console.Write("return " + x + " * Pow(" + x + ", " + y + " - 1) = " + logPow(x,y-1) + " \n");
                return x * Pow(x, y - 1);
            }
        }
        static void Main() {
            Console.Write("Last Result : " + Pow(2, 5)); 
        }
    }
}

Which gives the result :

Recursive action[1] Y status [5] : return 2 * Pow(2, 5 - 1) = 32 
Recursive action[2] Y status [4] : return 2 * Pow(2, 4 - 1) = 16 
Recursive action[3] Y status [3] : return 2 * Pow(2, 3 - 1) = 8 
Recursive action[4] Y status [2] : return 2 * Pow(2, 2 - 1) = 4 
Recursive action[5] Y status [1] : return 2 * Pow(2, 1 - 1) = 2 
Recursive action[6] Y status [0] : return 1.0 = 2 
Last Result : 32

You can debug your code by looking at these details. Also you can have fun with it using this link : https://onlinegdb.com/Bysbxat9H





pow