# How does the factorial function recursion work?

Page 1 of 1

## 4 Replies - 8979 Views - Last Post: 30 May 2014 - 05:39 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=118734&amp;s=71a3013b611dfef8b04d1138cd39b2db&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 Einsteinmc2300

Reputation: 1
• Posts: 29
• Joined: 01-July 09

# How does the factorial function recursion work?

Posted 06 August 2009 - 02:39 AM

``` int factorial (int num)
{
if (num==1)
return 1;
return factorial(num-1)*num; // recursive call
}

```

that's the code that I have although I'm not sure how it works.

My real problem with understanding this is ... well for example

if you're input is 5 (5! is 120) and it goes through the loop once it should get num=4 while 5*4 is 20 right? Well where the heck is 20 stored? It must be stored SOMEWHERE for it to be multiplied by 3 and then by 2 , correct?

So my question is how and why and where is the result (20,60,120) stored? There is only 1 variable and I'm pretty damn sure that 1 variable cannot store 2 pieces of data.

my friend told me the result is stored temporarily while it calculates but in no manner does my code ever tell the computer that there is a RESULT variable which stores the result.

how can it keep track of the multiplied number AND the current num value? that is confusing to me. Maybe I don't understand the process of recursion or something but tell me if i'm wrong

if num=5

then num=4

then num=3

then num=2

then num=1

then which variable is left to spit out 120?

I'm so confused and frustrated.

Just to state what I'm trying to say one more time and more clearly:

My idea of this function is that it stores 5 in num. Then turns 5 to 4 so it forgot about 5 already. and then it says *num. so what the heck happens? Or does it still remember 5?

Please show me the logic !!!! I have lost all faith in computing at the moment. If there is no logic in this I'll be in deep depression for a year

Is This A Good Question/Topic? 1

## Replies To: How does the factorial function recursion work?

• D.I.C Regular

Reputation: 9
• Posts: 419
• Joined: 08-April 09

## Re: How does the factorial function recursion work?

Posted 06 August 2009 - 03:20 AM

Never ever asked such a question before. Just figured if it works thats great. I'm no expert, but will try my brain at it.

You know how most function that inputs stuff usually expects something to output, in the case of a return at the end of any non-void function. Well, if you do a trace table thing, you are input 5 as num then, like you said 5 x 4 is 20, now if you type a cout in the function you will get the outputs, again like you've said, one after the other.

your
```return factorial(num-1)
```

I'm guessing, is where you temporary variables are stored.

### #3 Tom9729

• Segmentation fault

Reputation: 181
• Posts: 2,642
• Joined: 30-December 07

## Re: How does the factorial function recursion work?

Posted 06 August 2009 - 05:46 AM

Recursion is kind of confusing, if I could think of a good way to explain it I would probably be a discrete math teacher.

Let's do something like factorial(3) because it's shorter...

num = 3, since num is not zero we want to return factorial(2) * 3. We need to figure out the value of factorial(2) before we can go any further...

num = 2, since num is not zero we want to return factorial(1) * 2. We need to figure out the value of factorial(1) before we can go any further...

num = 1, since num is not zero we want to return factorial(0) * 1. We need to figure out the value of factorial(0) before we can go any further...

num = 0, since num is zero we want to return 1.

Now we know factorial(0) = 1, so factorial(0) * 1 = 1

Now we know factorial(1) = 1, so factorial(1) * 2 = 2

Now we know factorial(2) = 2, so factorial(2) * 3 = 6

so factorial(3) = 6

----

I believe that num is stored on the stack, and when you do a function call the stack is saved and restored after the function call is complete.

http://www.tenouk.co...overflow2a.html

### #4 premacutie

Reputation: 0
• Posts: 1
• Joined: 27-February 11

## Re: How does the factorial function recursion work?

Posted 30 May 2014 - 04:22 AM

Einsteinmc2300, on 06 August 2009 - 02:39 AM, said:

``` int factorial (int num)
{
if (num==1)
return 1;
return factorial(num-1)*num; // recursive call
}

```

that's the code that I have although I'm not sure how it works.

My real problem with understanding this is ... well for example

if you're input is 5 (5! is 120) and it goes through the loop once it should get num=4 while 5*4 is 20 right? Well where the heck is 20 stored? It must be stored SOMEWHERE for it to be multiplied by 3 and then by 2 , correct?

So my question is how and why and where is the result (20,60,120) stored? There is only 1 variable and I'm pretty damn sure that 1 variable cannot store 2 pieces of data.

my friend told me the result is stored temporarily while it calculates but in no manner does my code ever tell the computer that there is a RESULT variable which stores the result.

how can it keep track of the multiplied number AND the current num value? that is confusing to me. Maybe I don't understand the process of recursion or something but tell me if i'm wrong

if num=5

then num=4

then num=3

then num=2

then num=1

then which variable is left to spit out 120?

/> I'm so confused and frustrated.

Just to state what I'm trying to say one more time and more clearly:

My idea of this function is that it stores 5 in num. Then turns 5 to 4 so it forgot about 5 already. and then it says *num. so what the heck happens? Or does it still remember 5?

Please show me the logic !!!! I have lost all faith in computing at the moment. If there is no logic in this I'll be in deep depression for a year />

### #5 Skydiver

• Code herder

Reputation: 6216
• Posts: 21,461
• Joined: 05-May 12

## Re: How does the factorial function recursion work?

Posted 30 May 2014 - 05:39 AM