Jump to content

  • Log In with Google      Sign In   
  • Create Account


How C# computes Recursion


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
4 replies to this topic

#1 Thomas Wiborg   GDNet+   -  Reputation: 930

Like
1Likes
Like

Posted 04 October 2013 - 01:48 AM

Hello guys, I have this set of code
 

class Factorial
    {
        public int Fac(int x)
        {
            if (x == 1)
            {
                return 1;
            }
            else
            {
                return x * Fac(x - 1);
            }
        }
    }


 static void Main(string[] args)
        {
            Factorial fac1 = new Factorial();
            Console.WriteLine(fac1.Fac(4));   
            Console.ReadLine();
        }

The thing is, I know how factorial works. Like 4! = 4*3*2*1 = 24

But i dont see how the computer computes it. The debugging and breakpoints make me more confused. Does anyone have the time to explain me in detail how this works?

One of my way of thinking is:

First iteration:
return x * Fac(x - 1);    = 4 * 3;
Second:
x * Fac(x - 1);              = 3 * 2
Third
x * Fac(x - 1);              = 2 * 1

But nothing returns 24.

Tho I know that in the end the computer does 4*6 = 24

Thanks for all reply!

Thomas


Edited by Thomas Wiborg, 04 October 2013 - 01:50 AM.


Sponsor:

#2 Alpha_ProgDes   Crossbones+   -  Reputation: 4688

Like
6Likes
Like

Posted 04 October 2013 - 02:40 AM

class Factorial
    {
        public int Fac(int x)
        {
            if (x == 1)
            {
                return 1;
            }
            else
            {
                return x * Fac(x - 1);
            }
        }
    }

Note this is going to be long.

 

So let's start with Fac(4)

public int Fac(4)
{
     if (4 == 1)
     {
          return 1;
     }
     else
     {
          return 4 * Fac(4 - 1);  // now Fac(4 - 1) is going to be called while the Fac(4) waits for the result of Fac(4 - 1)
     }
}

public int Fac(3)
{
     if (3 == 1)
     {
          return 1;
     }
     else
     {
          return 3 * Fac(3 - 1);  // now Fac(3 - 1) is going to be called while the Fac(3) waits for the result of Fac(3 - 1)
     }
}
public int Fac(2)
{
     if (2 == 1)
     {
          return 1;
     }
     else
     {
          return 2 * Fac(2 - 1);  // now Fac(2 - 1) is going to be called while the Fac(2) waits for the result of Fac(2 - 1)
     }
}
public int Fac(1)
{
     if (1 == 1)
     {
          return 1;
     }
     else
     {
          return 1 * Fac(1 - 1);  // this line will never be called because we have reached the base case above
     }
}

So now the function returns like so...

 

We know that Fac(1) returns 1.

public int Fac(2)
{
     if (2 == 1)
     {
          return 1;
     }
     else
     {
          return 2 * 1; // Fac(2 - 1) returns 1
     }
}
public int Fac(3)
{
     if (3 == 1)
     {
          return 1;
     }
     else
     {
          return 3 * 2; // Fac(3 - 1) returns 2
     }
}
public int Fac(4)
{
     if (4 == 1)
     {
          return 1;
     }
     else
     {
          return 4 * 6; // Fac(4 - 1) returns 6
     }
}

So now Fac(4) returns 24. And program finished.

 

 

Note: I laid this out this way more for those who are complete beginners at recursion than for you.


Edited by Alpha_ProgDes, 04 October 2013 - 02:42 AM.

Beginner in Game Development? Read here.
 
Super Mario Bros clone tutorial written in XNA 4.0 [MonoGame, ANX, and MonoXNA] by Scott Haley
 
If you have found any of the posts helpful, please show your appreciation by clicking the up arrow on those posts Posted Image
 
Spoiler

#3 eppo   Crossbones+   -  Reputation: 2367

Like
6Likes
Like

Posted 04 October 2013 - 02:41 AM

This is what your code does:

 

Fac(4)

= 4 * Fac(3)

= 4 * (3 * Fac(2))

= 4 * (3 * (2 * Fac(1)))

= 4 * (3 * (2 * (1)))).

 

It helps if you look at it from the bottom up:

- the lowest argument for x is 1 which is simply returned as 1.

- the caller function (x = 2) takes that result, multiplies it with itself (2 * (1)) and returns it

- the caller of that function (x = 3) takes that result, multiplies it with itself (3 * (2)) and returns it

- the caller of that function (x = 4) takes that result, multiplies it with itself (4 * (6)) and returns it


Edited by eppo, 04 October 2013 - 02:51 AM.


#4 Thomas Wiborg   GDNet+   -  Reputation: 930

Like
4Likes
Like

Posted 04 October 2013 - 03:29 AM

Thanks alot ADP and Eppo!

And ADP for trying to turn my head around in the right direction, like 100times, lol !


Edited by Thomas Wiborg, 04 October 2013 - 03:29 AM.


#5 Alpha_ProgDes   Crossbones+   -  Reputation: 4688

Like
2Likes
Like

Posted 04 October 2013 - 03:32 AM

The TAIL recursion version of factorial

class Factorial
    {
        public int Fac(int x)
        {
             return FacAcc(x, 1);    
        }

        private int FacAcc(int x, int acc)
        {
             if (x == 0 || x == 1) return acc;
             else FacAcc(x - 1, acc * x);
        }
    }

Edited by Alpha_ProgDes, 04 October 2013 - 03:36 AM.

Beginner in Game Development? Read here.
 
Super Mario Bros clone tutorial written in XNA 4.0 [MonoGame, ANX, and MonoXNA] by Scott Haley
 
If you have found any of the posts helpful, please show your appreciation by clicking the up arrow on those posts Posted Image
 
Spoiler




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS