3
$\begingroup$

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.

  • 0
    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 program2012-07-03

4 Answers 4

5

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.

  • 0
    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.2012-07-04
5

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.

3

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.

  • 0
    **At my scholarship level, ** ... probably no sense in arguing about recursive/iterative with your friend, then.2012-07-03
1

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.