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.

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$ – Saurabh Jul 3 '12 at 17:18
5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – user1115057 Jul 4 '12 at 17:56
5
$\begingroup$

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.

$\endgroup$
0
3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – user1115057 Jul 3 '12 at 16:42
  • $\begingroup$ @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$$ $\endgroup$ – Thomas Russell Jul 3 '12 at 16:45
  • $\begingroup$ 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. $\endgroup$ – user1115057 Jul 3 '12 at 16:49
  • $\begingroup$ **At my scholarship level, ** ... probably no sense in arguing about recursive/iterative with your friend, then. $\endgroup$ – GEdgar Jul 3 '12 at 17:19
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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