2
$\begingroup$

The theorem of structured programming says that any algorithm can be expressed by those three control structures:

  1. Sequence
  2. Selection
  3. Iteration

Isn't it possible to rewrite any loop using a finite sequence of statements and choice between statements? Isn't this what compilers do? Can't we thus omit the third structure and stay equally expressive?

$\endgroup$
3
$\begingroup$

I convinced myself that this is not possible, I was indeed mixing up the selection structure with conditional jumps; but they're not equally expressive.

The conditional jump is as powerful as both selection and iteration together; this is what compilers use to rewrite both choice statements and loop statements.

As a counterexample for rewriting any loop using only the first two control structures, think of an infinite loop. This can not be rewritten using only sequence and selection while it can be rewritten using sequence and conditional jumps. So, we would lose expressiveness if we went without iterations.


Addendum to clear up the terminology:

  1. Sequence
  2. Selection (synonymous to choice), for example IF or SWITCH
  3. Iteration (synonymous to loop), for example WHILE or FOR
$\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.