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 was debating with someone about iterative vs recursive in programming. I was defending the iterative side. He then said me that the true definition of Fibonacci number is this: $$f(n) = f(n-1) + f(n-2);\space n > 2$$ with $f(0) = 0$ and $f(1) =1$.

Then I replied with the factorial example, because I had to admit that for this one, this was right, I don't see other definition. Factorial is defined with that recursive mathematical definition:

$$\operatorname{fact}(n)=\begin{cases}1 & \text{if } n=0 \\ n\cdot\operatorname{fact}(n-1) & \text{if } n > 0\end{cases}$$

But, in the same page, they also say that Factorial can be implemented iterative, and the mathematical definition, with the pseudo code that goes with it is:

function factorial is:
input: integer n such that n >= 0
output: [n × (n-1) × (n-2) × … × 1]

1. create new variable called running_total with a value of 1

2. begin loop
      1. if n is 0, exit loop
      2. set running_total to (running_total × n)
      3. decrement n
      4. repeat loop

3. return running_total

end factorial

$$fact(n) = fact_{acc}(n, 1)$$ $$\operatorname{fact_{acc}}(n, t)=\begin{cases}t & \text{if } n=0 \\ \operatorname{fact_{acc}}(n-1, n\cdot{t}) & \text{if } n > 0\end{cases}$$

Then he replied me that its not a iterative mathematical definition, but another recursive mathematical definition. But, if you check the source (I know that Wikipedia is not the best source, but...), It clearly state that its the representation of the iterative pseudo code.

The way I read it, is as long as n>0, repeat the content of the function and decrease n. t is used as an accumulator, and when n reach 0, we simply keep the result of what t contain.

Is it a mathematical definition of a recursive or iterative function? If its not an iterative definition, how a iterative mathematical definition for that factorial look like? (Not the code to implement it, the mathematical definition). If there is no way to represent that function with a iterative mathematical definition, can you show some example of very easy to understand iterative mathematical definition, and explain me how to read such definition?

Don't point me out to this: Factorial Function - Recursive and iterative implementation, Its only the implementation, it don't really talk about the mathematical definition. Im only interested by the mathematical definition, nothing else.

Edit: Want to thanks Shaktal who edited my post, and added some formatting. From the formatting he did to the 2 first mathematical definition of the function, was able to format the rest.

I want to thanks everyone for the clarification about mathematical definition and the implementation. Thanks for your comprehension, I will only see those thing in math next scholar year, but already saw recursion and iterative long time ago in programming.

share|improve this question
    
For any recursive program there exist iterative program and vice-versa. In mathematics there are many forms of the same things but I didn't come across any iterative definitions it is just how you implement in your program –  Saurabh Jul 3 '12 at 17:18
add comment

4 Answers 4

up vote 5 down vote accepted

The usual mathematical definition of factorial is $n! = \prod_{j=1}^n j$. I would say this is neither "iterative" nor "recursive" in your sense: the distinction between those is a matter of implementation rather than mathematics. You might also like $n! = \int_0^\infty x^n e^{-x}\ dx$. Or an even more purely "declarative", combinatorial definition: $n!$ is the number of permutations of $n$ objects.

As for the Fibonacci numbers, you might like the following declarative definition: $F_n$ is the number of subsets of $\{1,2,\ldots,n-2\}$ that don't contain any two consecutive integers.

There is a notion of "recursive function" in mathematical logic, but that's something quite different.

share|improve this answer
    
Thanks for the clarification, then it that me and him where wrong, because the its the implementation that is recursive or iterative. Also, I see those mathematics definition on another angle, multiple way to interpret them. –  user1115057 Jul 4 '12 at 17:56
add comment

Mathematics is declarative (it tells you what the value of something is) whereas code is procedural (it tells how how to compute the value of something).

Therefore asking for an iterative definition of the factorial function doesn't really make any sense. Any definition you could write down would essentially be pseudocode for computing values of the factorial function.

An implementation of the factorial function can be either iterative or recursive, but the function itself isn't inherently either. Note that an implementation isn't necessarily either iterative or recursive. For example, here are three different definitions of the factorial function in the language Haskell:

fact 0 = 1
fact n = n * fact (n-1)

fact n = fact' 1 n
  where
    fact' a 0 = a
    fact' a b = fact' (a*b) (b-1)

fact n = product [1..n]

You might call the first definition recursive and the second definition iterative - and the final definition is a definition in terms of more primitive functions. But they all define the same function.

share|improve this answer
add comment

The factorial can be given by a simple recurrence relation. The elements of the sequence defined by $$\begin{eqnarray*} x_0 &=& 1 \\ x_{n} &=& n x_{n-1} \end{eqnarray*}$$ are indeed $x_n = n!$. The collection of pairs $\{(n,x_n)\}$ for $n=0,1,2,\ldots$ is a function. It would not, however, be called a recursive function.

An iterated function is of the form $$f^m(x) = \underbrace{(f\circ \cdots \circ f)}_{m\mathrm{\, times}}(x)$$ where $f^0(x) = x$. That is, $f^m(x)$ is $f$ applied to $x$ $m$ times. Try to build factorial out of such a function. Some examples for $m=1,2,\ldots$,

(1) if $f(n) = n$, $f^m(n) = n$,

(2) if $f(n) = n^s$, $f^m(n) = n^{s^m}$,

(3) if $f(n) = n!$, $f^m(x) = n\underbrace{!\cdots!}_{m}$.

The "iterative" definition of factorial given in your pseudocode is
$$\begin{eqnarray*} f(0,m) &=& m \\ f(n,m) &=& f(n-1,n m). \end{eqnarray*}$$ Then $f(n,1) = n!$. This is really a recurrence relation taking two variables.

share|improve this answer
add comment

There is not really such a thing as an iterative definition of a mathematical object (such as a function). You could refer to an iterative process in a definition, but the definition itself must describe the whole object in a finite amount of text. That being said, there is nothing against defining the factorial by $$ n! = \prod_{i=1}^ni \qquad\text{for }n\in\mathbb N $$ which has nothing recursive to it.

share|improve this answer
    
At my scholarship level, we are not suppose to know what is factorial, integral, derivative, what recursive mean... But I am the guy who like math and love learning new thing by myself, so I know what are these. But because we didn't learning that yet, I have some difficult with notation. Can you explain me what is the big PI symbol you used to define the factorial? The name of that notation or symbol, or a links to Wikipedia explaining it would be appreciated. By the way, I will learn all those thing maybe this year, I will finally be at college. –  user1115057 Jul 3 '12 at 16:42
    
@user1115057 If you're familiar with the big sigma notation, then big pi notation is the analog of that but for products, instead of sums, e.g. $$5!=\prod_{i=1}^{5}{i}=1\times2\times3\times4\times5$$ And: $$n!=\prod_{i=1}^{n}{i}=1\times2\times\cdots\times n$$ –  Shaktal Jul 3 '12 at 16:45
    
Yeah, I am more familiar with the big sigma, we used it one time at school last scholar year that just terminated 3 week ago, in physics class, but only one time. But i still remember how to use it, and when I do integral, I usually use that sigma notation. Thanks for the clarification. –  user1115057 Jul 3 '12 at 16:49
    
**At my scholarship level, ** ... probably no sense in arguing about recursive/iterative with your friend, then. –  GEdgar Jul 3 '12 at 17:19
add comment

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.