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.