Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have the function:

n! = n*(n-1)*(n-2)...* 3 * 2 * 1

Which I need to sketch an implementation recursively and iteratively.

Could anyone point me in the right direction? I am finding this rather difficult

share|improve this question
1  
What do you mean by "sketch as an implementation"? –  joriki Jan 10 '12 at 9:01
    
@joriki wish I knew. "Sketch out an iterative/recursive implementation" –  danRhul Jan 10 '12 at 9:03
1  
The person who assigned the homework might know what it means :) –  Mariano Suárez-Alvarez Jan 10 '12 at 9:04
    
@MarianoSuárez-Alvarez It's not homework. This is a question I was asked in an interview. Doubt I'd ever be faced with this question again, but just in case... –  danRhul Jan 10 '12 at 9:06
    
"Sketch out an implementation of the function" is completely different from "Sketch the function as an implementation". Presumably you're being asked to indicate how you'd implement the function recursively and iteratively, without necessarily giving all the details. –  joriki Jan 10 '12 at 9:06

4 Answers 4

up vote 2 down vote accepted

Doesn't "implementation" imply more of a programming than a math task? Anyway

Iterative

Iteration is - go through all numbers from 1 to n and do something with them. It's just the way one would usually explain the factorial. What could the operation be?

factorial = 1
for n = 1 to n, 
 // what operation to do here?
end

Recursive

What is the factorial of 0? We know - $1$, by definition. Now assume you knew what value $(n-1)!$ has. What value will $n!$ have?

This way, you can write a recursive definition (it's like backwards induction).

$$n! = \begin{cases}1 &\, \text{if } n = 0 \\ use\, (n-1)!\,here & \text{otherwise}\end{cases}$$

share|improve this answer
    
My first thought was programming but then the fact it asked me to sketch it basically freaked me out a bit –  danRhul Jan 10 '12 at 9:15

You can find lots of examples of this on the Web by searching for keywords like "functional programming" and "factorial". Here's one. The first code sample is an iterative implementation, the second one is a recursive implementation.

share|improve this answer

Iterative:

factorial(n)
   res = 1
   for(i=0, i<n){
    res*=(i+1)
   }

   return res

Recursive:

factorial(n)
   if(n==0)
     return 1

   else
     return factorial(n-1)*n
share|improve this answer

#include
int fact(int n) {
int x=1;
while(n>1)
{
x=n*fact(n-1);
}
return(x);
}
void main()
{
int n,fact1;
scanf("%d",&n);
fact1=fact(n);
printf("%d",fact1);
}

share|improve this answer
    
You should probably at least specify the language you're using. –  Cameron Buie Sep 19 '13 at 6:05
    
$\Huge{\tt C}$ . –  Felix Marin Sep 19 '13 at 7:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.