# Factorial Function - Recursive and iterative implementation

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

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

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}$$

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

-

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

-

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

-
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