The Loop repeat

Section 2.5 The Loop repeat_until

Loops allow us to repeat sequences of instructions. In a repeat_until -loop a sequence of instructions is repeatedly followed until a specified statement is true.

🔗

A repeat_until -loop starts with a repeat instruction and ends with a until instruction. The instructions between repeat and until are followed (in order) until the statement after until is true. If you follow the algorithm and get to the instruction until and the statement after until is false, you jump back to repeat and execute the first instruction after repeat.

🔗

Every time we follow the instructions between repeat and _until we call an iteration of the ( repeat_until )-loop. We call the first time we follow these instructions the first iteration and so on.

🔗

Our first algorithm with a repeat_until -loop subtracts \(2\) from a given natural number \(n\) until we get number that is less than \(2\text{.}\) When the number is even the output is \(0\) , when the number the output is \(1\text{.}\)

🔗

Algorithm 2.29. Even or odd.

Input: 🔗: a natural number \(n\) greater than \(1\)
🔗
Output: 🔗: \(0\)if \(n\) is even, \(1\) otherwise
🔗

repeat
1. let \(n:=n-2\)
  🔗
  
  🔗
🔗
🔗
until \(n\lt 2\)
🔗

🔗
return \(n\)
🔗

🔗

🔗

We now use Algorithm 2.29 to determine whether \(5\) is even or not.

🔗

Example 2.30. Algorithm 2.29 with input \(n=5\).

We follow the instructions of Algorithm 2.29 for the input \(n=5\text{.}\)

🔗

Input: \(n=5\)

🔗

repeat: A repeat_until -loop starts here
1. let \(n:=n-2\) : We have \(n=5\text{.}\) We compute \(n-2=5-2=3\) and assign this value to \(n\text{.}\) So now \(n=3\text{.}\)
  🔗
  
  🔗
🔗
🔗
until \(n\lt 2\text{:}\) We have \(n=3\text{.}\) Since the statement \(n\lt 2\) is false we repeat the instructions in the loop.
🔗

🔗

repeat: We continue in the repeat_until -loop.
1. let \(n:=n-2\) : We have \(n=3\text{.}\) We compute \(n-2=3-2=1\) and assign this value to \(n\text{.}\) So now \(n=1\text{.}\)
  🔗
  
  🔗
🔗
🔗
until \(n\lt 2\text{:}\) We have \(n=1\text{.}\) Since the statement \(n\lt 2\) is true we leave the loop and continue with Item 3.
🔗

🔗
return \(n\text{:}\) We return the value of \(n\) which is 1.
🔗

🔗

🔗

Output: \(n=1\)

🔗

In our next example, given a natural number \(n\) , computes the sum of the natural numbers up to \(n\text{.}\) In the algorithm, \(s\) is the sum so far and \(i\) is incremented in each iteration of the repeat_until loop. The algorithm computes \(1+2+3+\dots+(n-2)+(n-1)+n\text{.}\)

🔗

Algorithm 2.31. Sum up to.

Input: 🔗: a natural number \(n\)
🔗
Output: 🔗: the sum of the natural numbers up to \(n\text{.}\)
🔗

let \(i:=0\)
🔗

🔗
let \(s:=0\)
🔗

🔗
repeat
1. let \(i:=i+1\)
  🔗
  
  🔗
2. let \(s:=s+i\)
  🔗
  
  🔗
🔗
🔗
until \(i=n\)
🔗

🔗
return \(s\)
🔗

🔗

🔗

In the Example 2.32 we compute the sum of the natural numbers up to \(4\) with Algorithm 2.31.

🔗

Example 2.32. Algorithm 2.31 for the input \(n=4\).

We follow the steps of Algorithm 2.31 for the input \(n=4\text{.}\) For each step of the algorithm, we give the new values of the variables that change values in that step.

🔗

Input: \(n=4\)

🔗

1. let \(i:=0\) : So the variable \(i\) has the value \(0\) now.

🔗

2. let \(s:=0\) : So the variable \(s\) has the value \(0\) now.

🔗

3. repeat : A repeat_until -loop starts here.

🔗

3.a. let \(i:=i+1\) : As the old value of \(i\) was zero the new value of \(i\) is \(0+1=1\text{.}\)

🔗

3.b. let \(s:=s+i\) : As the old value of \(s\) was zero and the value of \(i\) is \(1\) the new value of \(s\) is \(0+1=1\text{.}\)

🔗

4. until \(i=n\) : As \(i=1\) and \(n=4\) the statement \(i=n\) is false. We repeat the loop and continue with step 3.a

🔗

3. repeat : We continue the A repeat_until -loop.

🔗

3.a. let \(i:=i+1\) : As the old value of \(i\) was \(1\) the new value of \(i\) is \(1+1=2\text{.}\)

🔗

3.b. let \(s:=s+i\) : As the old value of \(s\) was \(1\) and the value of \(i\) is \(2\) the new value of \(s\) is \(1+2=3\text{.}\)

🔗

4. until \(i=n\) : As \(i=2\) and \(n=4\) the statement \(i=n\) is false. We repeat the loop and continue with step 3.a.

🔗

3. repeat : We continue the A repeat_until -loop.

🔗

3.a. let \(i:=i+1\) : As the old value of \(i\) was \(2\) the new value of \(i\) is \(2+1=3\text{.}\)

🔗

3.b. let \(s:=s+i\) : As the old value of \(s\) was \(3\) and the value of \(i\) is \(3\) the new value of \(s\) is \(3+3=6\text{.}\)

🔗

4. until \(i=n\) : As \(i=3\) and \(n=4\) the statement \(i=n\) is false. We repeat the loop and continue with step 3.a.

🔗

3. repeat : We continue the A repeat_until -loop.

🔗

3.a. let \(i:=i+1\) : As the old value of \(i\) was \(3\) the new value of \(i\) is \(3+1=4\text{.}\)

🔗

3.b. let \(s:=s+i\) : As the old value of \(s\) was \(6\) and the value of \(i\) is \(4\) the new value of \(s\) is \(6+4=10\text{.}\)

🔗

4. until \(i=n\) : As \(i=4\) and \(n=4\) the statement \(i=n\) is true. We continue with step 5.

🔗

5. return \(s\) : The algorithm returns \(s=10\text{.}\)

🔗

Output: 10

🔗

In Example 2.33 click your way through the steps of Algorithm 2.31 to see how the values of the variables change with each instruction. When following the loop you have to click on repeat as well as until.

🔗

Example 2.33. Algorithm sum interactive.

🔗

In the video in Figure 2.34 we introduce repeat_until loops and consider Algorithm 2.31 and Algorithm 2.29 once more.

🔗

Figure 2.34. Algorithms -- Loopsby Matt Farmer and Stephen Steward

🔗

A repeat_until -loop with a statement that is always false in the repeat instruction yields a never ending loop. A sequence of instructions (even if this is only the case fore certain input values) that contains such a loop is not an algorithm.

🔗

Example 2.35. Infinite loop.

We give an example of a sequence of instructions that gets caught in a never ending loop for certain input values.

🔗

Input: an integer \(a\)

🔗

let \(m:=1\)
🔗

🔗
repeat
🔗
1. let \(m:=m\cdot a\)
  🔗
  
  🔗
2. let \(a:=a-1\)
  🔗
  
  🔗
🔗
until \(a=0\)
🔗

🔗
return \(m\)
🔗

🔗

🔗

When the input \(a\) is 0 or a negative integer, this sequence of commands does not end. It never reaches the instruction return \(m\) since \(a\) will never be 0. In this case we do not have a finite sequence of instructions, so it does not match the definition of an algorithm ( Definition 2.1 ).

🔗

Problem 2.36.

With the algorithm below answer the following questions:

Follow the steps of the algorithm for \(b=5\) and \(n=3\text{.}\)
🔗

🔗
What does the algorithm return for the input \(b=-2\) and \(n=6\text{.}\)
🔗

🔗
What does the algorithm compute?
🔗

🔗

🔗

Algorithm 2.37.

Input 🔗: An integer \(b\) and a natural number \(n\)
🔗
Output 🔗: An integer \(c\)
🔗

let \(c:=0\)
🔗

🔗
let \(i:=0\)
🔗

🔗
repeat
🔗
1. let \(c:= c+b\)
  🔗
  
  🔗
2. let \(i:= i+1\)
  🔗
  
  🔗
🔗
until \(i=n\)
🔗

🔗
return \(c\)
🔗

🔗

🔗

Solution.

We follow the algorithm for the input \(b=5\) and \(n=3\text{.}\) For each step with an assignment we give the new value of the variable.
🔗

Input: \(b=5\) and \(n=3\)
🔗

  1. \(c=0\)
🔗

  2. \(i=0\)
🔗

  3. A repeat_until -loop starts
🔗

  3.a. \(c=5\)
🔗

  3.b. \(i=1\)
🔗

  4. As \(i=1\) and \(n=3\) the statement \(i=n\) is false. We repeat the loop and continue with step 3.a.
🔗

  3. We continue in the repeat_until -loop.
🔗

  3.a. \(c=10\)
🔗

🔗
  3.b. \(i=2\)
🔗

  4. As \(i=2\) and \(n=3\) the statement \(i=n\) is false. We repeat the loop and continue with step 3.a.
🔗

  3. We continue in the repeat_until -loop.
🔗

  3.a. \(c=15\)
🔗

  3.b. \(i=3\)
🔗

  4. As \(i=3\) and \(n=3\) the statement \(i=n\) is false. We exit the loop and continue with step 5.
🔗

  5. We return the value of \(c\) which is \(15\text{.}\)
🔗

Output: 15
🔗

🔗
Proceeding as above we find that for the input \(b=-2\) and \(n=6\) the algorithm returns \(-12\text{.}\)
🔗

🔗
Until \(i\lt n\) the algorithm adds \(b\) to \(c\) and adds \(1\) to \(n\text{.}\) Thus the number of times \(b\) is added to \(c\) is \(n\text{.}\) As initially \(i\) is set to 0 (see step 2 ) the number of times \(b\) is added to \(0\) is \(n\text{.}\) So the output of the algorithm is \(n \cdot b\text{.}\) Also compare Definition 1.31 where we had defined multiplication as repeated addition.
🔗

🔗