Is this mathematical definition iterative? If not, what does an iterative function look like?

Question

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 any other definition. Factorial is defined by the following 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 iteratively, and the mathematical definition, with the pseudocode 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

$$\operatorname{fact}(n) = \operatorname{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 to me that it's not an 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 states that it's the representation of the iterative pseudocode.

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

Is the above a mathematical definition of a recursive or of an 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: https://math.stackexchange.com/questions/97820/factorial-function-recursive-and-iterative-implementation. It's only the implementation. It doesn't really talk about the mathematical definition. I'm only interested in the mathematical definition, nothing else.

Edit: I want to thank Shaktal who edited my post, and added some formatting. From the formatting he did to the 2 first mathematical definition of the function, I 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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.