CSIS 111B: Fundamentals of Computer Programming: Lessons

# Repetition Structures

## Objectives

By the end of this lesson you will be able to:

• Understand the types of control structures used in computer programming
• Understand how to implement a while loop repetition structure
• Understand how to implement a do-while loop repetition structure
• Understand how to implement a for loop repetition structure
• Understand how to implement a foreach loop repetition structure
• Understand how to implement recursion

## Introduction To Control Structures

The actions that a program takes are expressed in statements. Common actions include:

• declaring (initializing) variables
• assigning values
• calling methods or functions
• looping through collections based on one or more termination values
• branching to one or another block of code depending on a given condition

A statement can consist of a single line of code that ends in a semicolon, or a series of single-line statements in a block. A statement block is enclosed in {} brackets and can contain nested blocks.

An expression is a sequence of one or more operands and zero or more operators that can be evaluated to a single value, object, method, or namespace.

The order in which statements are executed in a program is called the flow of control (not to be confused with flow control) or flow of execution. The flow of control may vary every time that a program is run, depending on how the program reacts to input that it receives at run time. The emphasis on explicit control of flow distinguishes an imperative programming language from a declarative programming language.

According to the structured program theorem any computer program can be written using the 3 basic controls structures shown in figure 1. These structures are referred to as control structures because they give the programmer control over how the program flows.

The sequence control structure references the fact that in structured programming, the ordered sequencing of successive commands is considered one of the basic control structures, which is used as a building block for programs alongside iteration, recursion (also iteration) and choice (selection).

The selection (decision) control structure re-directs the program flow based on the evaluation of a Boolean expression. If the expressions evaluates to true one sequence of one or more statements are executed, if the expression evaluates to false then a different sequence of one or more statements will be executed.

The iteration (repetition) control structure will run a sequence of statements repeatedly while the termination expression evaluates to true.

In this, and the next lesson you will learn about each of these control structures and how to implement them at the code level. We start with repetition structures.

Visual Studio Solution for Tutorial 8

## Repetition Structures

All modern programming languages based on C have repetition structures. C# has four different control structures that allow programmers use to perform repetitive tasks:

1. The while loop
2. The do-while loop
3. The for loop
4. The foreach loop.

These repetition control structures can be used to execute the statements in the loop body a number of times, depending on the loop termination criterion.

A loop can also be terminated by using one of several control transfer statements that transfer control outside the loop. These statements are break, goto, return, or throw. Finally, the continue statement can be used to pass control to the next iteration of the loop without exiting the loop.

### A `while` Loop

The while loop repeatedly executes a block of statements until a specified boolean expression evaluates to false.

The general form of the while loop is as follows:

```        while (boolean test)
statement```

Here, a boolean test is performed at the beginning of the loop. If the test evaluates to true, the loop body executed and the test is performed again. If the test evaluates to false, the loop terminates and control is transfered to the next statement following the loop.

Because the boolean test is performed before the execution of the loop, it is possible that the body of the loop is never executed. This happens if the test evaluates to false the first time.

Take the following steps to create a program that uses the while loop:

1. Create a new C# Console application solution named RepetitionStructures in Visual Studio.
2. Type while_statement for the name of the new project.
3. Right-click on the newly added while_statement project and choose Set as StartUp Project from the context menu that appears.
4. Click anywhere in the Source code editor window and pres Ctrl + A on your keyboard to select all of the template code in your new project, and then press Delete.
5. Type the following code into the Source code window for your while_statement project and then press CTRL + F5 to run your while_statement project code without debugging.
```using System;

namespace while_statement
{
class Program
{
static void Main(string[] args)
{
int i = 1;
while (i <= 5)
{
Console.WriteLine("The value of i = {0}", i);
i++;
}
}
}
}                ```

In this example, the variable `i` is initialized as an integer type and assigned the value of 1. Next the condition in the while loop is evaluated. Because the condition is `true` (1 <= 5), the code within the while statement block is executed. The value of `i` is written in the command window, and then the value of `i` is increased by 1 so it becomes 2. Control then passes back to the while statement, and the condition is again evaluated. Because the condition is still `true` (2 <= 5), the statement block is executed again. The loop continues until the value of `i` becomes 6 and the condition in the while statement becomes `false` (6 <= 5). The above program, when executed, generates the following output:

In most cases, to have a well-designed while loop, you must have three parts:

1. Initializer: The initializer sets the loop counter to the correct starting value. In our example, the variable i is set to 1 before the loop begins.
2. Loop test: The loop test specifies the termination condition for the loop. In our example, the expression (i <=5) is the condition expression.
3. Termination expression: The termination expression changes the value of the loop counter in such a way that the termination condition is achieved. In our example the expression i++ is the termination expression.

The flowchart equivalent of this while loop looks like this:

### The `do while` Loop

The do-while loop repeatedly executes a block of statements until a specified boolean expression evaluates to false. The do-while loop tests the condition at the bottom of the loop. This allows for the do-while loop statement block to run at least on time before the termination condition is tested.

The general form of the do-while loop is as follows:

```        do
statement
while (boolean test)```

Take the following steps to create a program that uses the do-while loop:

1. Open your RepetitionStructures solution in Visual Studio
2. Add a new C# Console Application project to the solution and name it dowhile_statement.
3. Right-click on the newly added dowhile_statment project and choose Set as StartUp Project from the context menu that appears.
4. Click anywhere in the Source code editor window and pres Ctrl + A on your keyboard to select all of the template code in your new project, and then press Delete.
5. Type the following code into the Source code window for your dowhile_statement project and then press CTRL + F5 to run your dowhile_statement project code without debugging.
```using System;

namespace dowhile_statement
{
class Program
{
static void Main(string[] args)
{
int i = 1;
do
{
Console.WriteLine("The value of i = {0}", i);
i++;
}
while (i <= 5);
}
}
} ```

In this example, after the variable `i` is assigned the value of 1, control directly enters the loop. At this point, the code within the do-while statement block is executed. Specifically, the value of `i` is written in the command window and the value of `i` is increased by 1 so that it becomes 2. Next, the condition for the do-while loop is evaluated. Because the condition evaluates to true (2 <=5), control passes back to the do-while statement, and the statement block is executed again. The loop continues until the value of `i` becomes 6 and the termination condition evaluates to `false` (6 <= 5). This example, when executed, generates the same output as the `while_statement` program demonstrated previously.

The choice between a while loop and a do-while loop depends on whether you want the loop to execute at least once. If you want the loop to execute zero or more times, choose the while loop. In contrast, if you want the loop to execute one or more times, choose the do-while loop.

The best analogy here is that of a cook wanting to test their soup to see if it is salty enough. If the procedure of choice is to taste the soup first to determine if more salt is needed, then a while loop works best, however if you want to add salt first and then taste the soup for saltiness, a do-while loop would be most appropriate.

### The `for` Loop

The for loop combines the three elements of iteration — the initialization expression, the termination condition expression, and the counting expression — into a more readable code structure.

The for loop is similar to the while loop; it allows a statement or statement block to be executed repeatedly until an expression evaluates to false. The general form of the for loop is as follows:

```        for (init-expr; cond-expr; count-expr)
statement```

As you can see the for loop combines the three essential control expressions of an iteration. This results in more readable code. The for loop is especially useful for creating iterations that must execute a specified number of times.

Take the following steps to create a program that uses a for loop:

1. Open your RepetitionStrutures solution in Visual Studio
2. Add a new C# Console Application project to the solution and name it for_statement.
3. Right-click on the newly added for_statement project and choose Set as StartUp Project from the context menu that appears.
4. Click anywhere in the Source code editor window and pres Ctrl + A on your keyboard to select all of the template code in your new project, and then press Delete.
5. Type the following code into the Source code window for your for_statement project and then press CTRL + F5 to run your for_statement project code without debugging.
```        using System;

namespace for_statement
{
class Program
{
static void Main(string[] args)
{
for (int i = 1; i <= 5; i++)
{
Console.WriteLine("The value of i = {0}", i);
}
}
}
}            ```

This code when executed, generates the same output as the `while_statement` code above. Here, the variable `i` is initialized within the scope of the for statement and its value is assigned to 1. The loop continues as long as the value of `i` is less than or equal to 5. After the loop body, the counter expression is evaluated and the control goes back to the conditional expression.

All the control expressions for the loop are optional. For example, you can omit all the expressions to create an infinite loop like this:

```        for (; ;)
{
//do nothing
} ```

#### While/For Examples

###### C#

Here is how the code in our `Program.cs` file will look. Place the code inside the Main() method and run it.

```string[] myArray = new string[10];
int counter = 0; //Initializer

while (counter < myArray.Length) //Loop test (condition expression)
{
Console.Write("{0}. Enter a number: ", counter + 1);
counter++; //Termination expression
}

Array.Sort(myArray);

for (var i = 0; i < myArray.Length; i++)
{
Console.WriteLine("Element {0} is: {1}", i, myArray[i]);
}```

### The `foreach` Loop

The foreach loop is useful for iterating through the elements of a collection.

The foreach loop can be thought of as an enhanced version of the for loop for iterating through collections such as arrays and lists. The general form of the foreach statement is as follows:

```        foreach (ElementType element in collection)
statement            ```

The control expression for the foreach loop must be placed inside parenthesis. If more than one statement needs to be executed as part of the loop, these statements must be placed together inside curly braces.

Take the following steps to create a program that show how the foreach loop provides a simple way to iterate through a collection:

1. Open your RepetitionStructures solution in Visual Studio
2. Add a new C# Console Application project to the solution and name it foreach_statement.
3. Right-click on the newly added project and choose Set as StartUp Project from the context menu that appears.
4. Click anywhere in the Source code editor window and pres Ctrl + A on your keyboard to select all of the template code in your new project, and then press Delete.
5. Type the following code into the Source code window for your foreach_statement project and then press CTRL + F5 to run your foreach_statement project code without debugging.
```using System;

namespace foreach_statement
{
class Program
{
static void Main(string[] args)
{
int[] numbers = { 1, 2, 3, 4, 5 };
foreach (int i in numbers)
{
Console.WriteLine("The value of i = {0}", i);
}

}
}
}            ```

In this example, the loop sequentially iterates through every element of the collection, numbers it, and displays it in the command window. The method generates the same output as the `for_statement` above.

### Recursion

Recursion is a programming technique that causes a method to call itself in order to compute a result.

Recursion is iteration related. You can write a method that generates the same results with either recursion or iteration. Usually, the nature of the problem itself will help you choose between iterative or a recursive solution. For example, a recursive solution is more elegant when you can define the solution of a problem in terms of a smaller version of the same problem.

To better understand this concept, take the example of the factorial operation from mathematics. The general recursive definition for n factorial (written n!) is as follows.

According to this definition, if the number is 0, the factorial is one. If the number is larger than zero, the factorial is the number multiplied by the factorial of the next smaller number. For example, you can break 3! like this: 3! = 3 * 2! = 3 * 2* 1! = 3 * 2 * 1 * 0! = 3 * 2 * 1 * 1 = 6

Take the following steps to create a C# program that presents a recursive solution to a factorial problem:

1. Open your RepetitionStructures solution in Visual Studio
2. Add a new C# Console Application project to the solution and name it Factorial.
3. Right-click on the newly added project and choose Set as StartUp Project from the context menu that appears.
4. Click anywhere in the Source code editor window and pres Ctrl + A on your keyboard to select all of the template code in your new project, and then press Delete.
5. Type the following code into the Source code window for your Factorial project and then press CTRL + F5 to run your Factorial project code without debugging.
```namespace Recursion
{
class Program
{
static void Main(string[] args)
{
Factorial(5);
}

public static int Factorial(int n)
{
if(n==0)
{
return 1; //base case
}
else
{
return n * Factorial(n - 1); //recursive case
}
}
}
}```

In your code editor, add a breakpoint at line 11 - the opening curly brace for the Factorial() method. Run your code in Debug mode (F5 in Visual Studio) and watch the value of "n" change in your debug window (in Visual Studio: Debug --> Windows --> Autos)

As seen in this example, a recursive solution has two distinct parts:

1. Base case: This is the part that specifies the terminating condition and doesn't call the method again. The base case in the factorial method is n == 0. If you don't have a base case in your recursive algorithm, you create an infinite recursion. An infinite recursion will cause your computer to run out of memory and throw a `System.StackOverflowException` exception.
2. Recursive case: This is the part that moves the algorithm toward the base case. The recursive case in the `Factorial` method is the else part, where you call the method again but with a smaller value progressing toward the base case.

#### Recursion Examples

###### C#
```using System;

namespace Recursion
{
public class Program
{
static public void Main()
{
Console.WriteLine(\$"Factorial of {number} is: {ComputeFactorial(number)}");
}

private static int ComputeFactorial(int number)
{
int factorial = 1;

while (number > 1)
{
factorial *= number--;
}

return factorial;
}
}
}```

## Summary

In this lesson you learned about the types of control structures used in computer programming, how to implement a while loop repetition structure, how to implement a do-while loop repetition structure, how to implement a for loop repetition structure, how to implement a foreach loop repetition structure, and how to implement recursion.