4 Replies - 8480 Views - Last Post: 30 May 2014 - 05:39 AM Rate Topic: -----

#1 Einsteinmc2300  Icon User is offline

  • New D.I.C Head

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

How does the factorial function recursion work?

Post icon  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 :ph34r:

Is This A Good Question/Topic? 1
  • +

Replies To: How does the factorial function recursion work?

#2 ladyinblack  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 9
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#3 Tom9729  Icon User is offline

  • Segmentation fault
  • member icon

Reputation: 180
  • View blog
  • Posts: 2,641
  • 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.

More information here...

http://www.tenouk.co...overflow2a.html
Was This Post Helpful? 0
  • +
  • -

#4 premacutie  Icon User is offline

  • New D.I.C Head

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

Re: How does the factorial function recursion work?

Posted 30 May 2014 - 04:22 AM

View PostEinsteinmc2300, 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 :ph34r:/>

Was This Post Helpful? 0
  • +
  • -

#5 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3540
  • View blog
  • Posts: 10,958
  • Joined: 05-May 12

Re: How does the factorial function recursion work?

Posted 30 May 2014 - 05:39 AM

Please do not necro old posts. Create a fresh one of your own. Closing this thread.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1