• 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.

4 replies to this topic

#1Thomas Wiborg  Members

1573
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));
}


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

Thomas

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

#2Alpheus  GDNet+

6813
Like
6Likes
Like

Posted 04 October 2013 - 02:40 AM

POPULAR

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.

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.

External Articulation of Concepts Materializes Innate Knowledge of One's Craft and Science

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

Spoiler

#3eppo  Members

4601
Like
6Likes
Like

Posted 04 October 2013 - 02:41 AM

POPULAR

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.

#4Thomas Wiborg  Members

1573
Like
4Likes
Like

Posted 04 October 2013 - 03:29 AM

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.

#5Alpheus  GDNet+

6813
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.

External Articulation of Concepts Materializes Innate Knowledge of One's Craft and Science