-
Recursion
I'm having trouble understanding the following code fragment. Should it return 3 * 3=9
Code:
#include <stdio.h>
int factorial(int num);
void main()
{
int fact, num=3;
fact = factorial(num);
printf("%d factorial = %d\n", num, fact);
}
int factorial(int num)
{
/* num factorial. Assumes num >= 1 */
if (num == 1) return 1;
else return (num * factorial(num-1));
}
-
it should return 3*2*1. Try putting a printf function in the factorial function so you can see whats happening.
-
i still don't understand it, i tried the iterated version:
Code:
#include <stdio.h>
int factorial(int num);
void main()
{
int fact, num=4;
fact = factorial(num);
printf("%d factorial = %d\n", num, fact);
}
int factorial(int num)
{
/* num factorial. Assumes num >= 1 */
int i, fact=1;
for (i=2; i<=num; i++)
{
fact *= i;
printf("\n%d\n", i);
}
printf("\n");
return fact;
}
but it doesn't add up:
i = 2
i = 3
i = 4
4 factorial = 24
2*1(fact) = 2
3*1(fact) = 5
4*1(fact) = 10
hmm?:|
-
Four factorial is 24.
...that's what I got on the program.
-
A factorial is the result of multiplying a number by all number less then that number. Such as 4*3*2*1=24
the for loop counts from 2 to the number who's factorial you want.
This line multiplies fact by i so the result of going thru the loop is
i=2 fact*2=2
i=3 fact*3=6
i=4 fact*4=24
Multiplyig by 1 has no affect so there is no need to start the loop with i equal to 1
-
Yeah 1*2*3*4 = 24. I just don't get what fact *= i;
does.
To me it reads
1*1= 1
2*1 = 3 (incremented from previous value)
3*1 = 6 (incremented from previous value)
4 * 4 = 22 (incremented from previous value)
why is it not 24?:|
-
Quantum,
i=2 fact*2
i=3 fact*3
i=4 fact*4
gives me 16.
-
fact *= i; means to multiply fact by i and store the result in fact.
-
"Fact *= i" is the equivilent of "Fact = Fact * i;"
In otherwords
fact = 1 * 4
i - 1
fact = 4 * 3
i - 1
fact = 12 * 2
i - 1
fact = 24 * 1
fact = 24
-
thanks guys, the *= expression confused me a bit, and the recursion bit made it even more confusing since i didn't understand the iterated version.
-
> void main()
And 200+ posts - tsk
-
Heh, i didn't write the code. It was from an example in a book. I know that void main is a big no no. Since when did post count equate to > knowledge?
tsk.tsk.
-
The theory is that if you've made 200 posts to this site, the chances are you've posted a program before, and if you used void main, you'd have been told off, and learned to not do it again. :)
-
nope, i don't believe i've used void main anywhere. Like i said it was specifically with this example. Thanks for your help everyone.
-
Just a quick addition to the commentary.
The definition of factorial is recursive.
For all whole numbers greater than 1, in algebraic notation: n! = n * ((n-1)!)
By definition, 1! = 1
So:
Code:
1! = 1
2! = 2 * 1! = 2 * 1 = 2
3! = 3 * 2! = 3 * 2 * 1! = 3 * 2 * 1 = 6
4! = 4 * 3! = 4 * 3 * 2! = 4 * 3 * 2 * 1! = 4 * 3 * 2 * 1 = 24
5! = 5 * 4! = 5 * 4 * 3! = 5 * 4 * 3 * 2! = 5 * 4 * 3 * 2 * 1! = 5 * 4 * 3 * 2 * 1 = 120
and so on. You will note that all factorial values other than 1! are even.