I was reading a Wikipedia page on Primitive Recursive Functions but there is a phrase for describing the simple for loops which I really don't understand. Can anyone explain this to me?
The Phrase: An upper bound of the number of iterations of every loop can be determined before entering the loop
The Wikipedia page
The Wikipedia statement is informal and quite ambiguous. For example, let $A(n,n)$ be the Ackermann function, and consider the following program, where $n$ is the input:
x ← 0
for i from 1 to A(n,n):
x ← x + 1
return x
This function is not primitive recursive, although there is a bound on the number of iterations which is known ahead of time.
A better explanation is the LOOP programming languages. Every loop in LOOP runs $x_i$ times, where $x_i$ is a variable, and the number of iterations is the value of $x_i$ before the loop is run. For example:
LOOP x DO
x ← x + 1
END
is a problem that doubles $x$, and
z ← 0
LOOP x DO
z ← z + 1
END
LOOP y DO
z ← z + 1
END
is a problem that assigns $x + y$ to $z$.
A function can be computed in LOOP (using a reasonable input/output convention) iff it is primitive recursive. So if you only allow loops in which the number of iterations is the value of some variable just before the loop, then the resulting function will be primitive recursive, and furthermore, every primitive recursive function can be computed only using such loops.
This line is quite self describing. Still, let me explain a bit. for loops works in a specific range of values. For example: When you iterate over an array, knowingly or unknowingly you known the length of that array, which means that you know the no. of iterations your loop will perform.
Take a look at the pseudo code below:
FRUITS = ["APPLE", "BANANA", "MANGO"]
FOR FRUIT OF FRUITS
PRINT FRUIT
Above, the for loop will run 3 times, hence you know the no. of iterations before you even start that.
I hope know you understood that line well.
