0

In the book Introduction to Algorithms, there is a line under the heading Analysis of Insertion Sort that reads:

"When a for or while loop exits in the usual way (i.e., due to the test in the loop header), the test is executed one time more than the loop body."

The for loop, as far as I understand, uses a counter for the iterating variable. So, for example, by executing the code:

for j in range(0,3):
     print(j)

in python, we get the result:

0
1
2

The iterating variable j only goes through the values 0, 1 and 2. So the for loop and the body of the loop both execute only thrice.

A similar question has been asked here: Why are loops executed one more time than the loop body?

However, I reckon that the OP confused the mechanism of for loop with while loop. The answers to the question seem to support his misconception.

phuclv
  • 37,963
  • 15
  • 156
  • 475
Shiladitya Mukherjee
  • 65
  • 1
  • 7
  • The book is talking about the underlying implementation of the loop, and it is talking about the **test** for the loop condition, not about the code inside the loop. In Python, the test for the loop condition is done behind the scenes, and is not reflected by the `for` loop code in any way. It does not make sense to ask this question with a Python code example. – Karl Knechtel Oct 08 '22 at 06:16

2 Answers2

3

That is because there is always one more evaluation of the condition of the loop than there are executions of the body of the loop.
Take this simple example:

x = 4
while x < 0:
    x += 1
    print('hello')

We can see that the body of the loop is never executed (0 times), while the exit condition of the loop is evaluated once(1 time).
So, in any situation, we have the following:
The body of the loop is executed once for every time the condition is evaluated to True
AND
The condition is one more time evaluated to False, for the program to exit the loop.

m.raynal
  • 2,983
  • 2
  • 21
  • 34
  • I think I did, maybe your question is not stated so clearly. The thing is there is no such thing as "execution of the for loop". You can execute its body, you can evaluate its condition, but you don't *execute* a loop – m.raynal Jul 17 '19 at 11:34
  • I have a confusion in the mechanism of for loop.I understand how the while loop works. I clearly stated that this was the point of confusion in the question whose link I have provided. There, in my opinion, the OP mixed up the while loop and the for loop. – Shiladitya Mukherjee Jul 17 '19 at 11:37
  • 1
    Then it might be useful to consider the for loop in another language such as `C` or `java`. They use the 3 arguments form (initialize, iterate, end condition), which allows to understand better the way they work. With the example you provide, you use `range` which is *sortof* a generator, and iterating on a generator is yet another story. In python, `for` uses syntactic sugars to make it look beautiful, without letting the reader see what really happens in the detail. – m.raynal Jul 17 '19 at 11:46
  • 1
    Now that I have learned C++ quite a bit, I completely understand your point. :D – Shiladitya Mukherjee Dec 12 '19 at 09:01
-1

In your Python example, do_something() in the loop

for j in range (0,n):
    do_something()

is executed n-1 times because the upper bound of the range is non-inclusive. So it will be executed when j=0, j=1, ... j = n-1. The loop itself will execute one more time (i.e. when j=n) and see that the value is no longer in range and will not execute the body.

So that is why the for-loop executes one more time than the body.

The same reasoning applies to for loops of course.

Matti
  • 191
  • 1
  • 14
  • I thought the for loop worked like: when you reach j=n-1, do_something and exit the loop. That way the for loop and the body of the loop execute same number of times. – Shiladitya Mukherjee Jul 17 '19 at 11:34
  • No, the for loop will perform an exit condition in order to break the loop. That exit condition would be when j no longer is in the range. In this case, once j = n, the for loop will see that j is no longer in range (because the upper bound is non-inclusive), and will perform the exit condition and break. – Matti Jul 17 '19 at 11:40
  • 1
    "is executed n-1 times because the upper bound of the range is non-inclusive." This is wrong. It executes n times. "So it will be executed when j=0, j=1, ... j = n-1." Correct. That is n different values, not n-1. Notice how, when you count objects in real life, you start at 1, but the loop over the `range` starts at `0`? But all of this is talking about the problem at completely the wrong level, because `range` is **not part** of the Python `for` loop syntax; it is **just** a *perfectly ordinary* class (in 3.x) that represents a sequence of numbers, or a function (in 2.x) that creates a list. – Karl Knechtel Oct 08 '22 at 06:18