In: Computer Science
Python Loop invariant
To show that an assertion A is a loop invariant , is it enough to argue that the execuation of the loopbody preserves A? Please desscribe it throughly.
On each loop we write, we should always ask this crucial question:
Say that several iterations of the loop have been running; what has it achieved so far?
The response to the factorial illustration is:
Factor fact has the meaning following i iterations, fac = = i!.
This response is significant because it demonstrates the method used by the loop to achieve its target in stages: as i count upwards towards n, fac = = i That holds true repeatedly. And when i = = n, the loop ends, this means that the loop can accomplish its goal: fac = = n!.
The answer to the "key question" mentioned above is the invariant property of the loop.
This is because the output from the previous iterations of the loop flows into the next iteration of the loop. So, iteration after iteration after iteration, whatever is done looks the same. This is a logical property which can be demonstrated.
The argument that results from performing one more iteration of the loop is the same as the statement we had when we began the iteration.