Loops in a flowchart: an arrow that goes back up
Published . By the DiagramDesk team.
A flowchart has no loop symbol. A loop is a decision with one of its answers leading back to an earlier step, and once you can see that shape you can draw any loop a course will ask for. Three classic exercises show the three ways it gets used.
Anatomy of a loopFactorialFibonacciPrime test
Four parts, always in the same order
Every counting loop in a flowchart has the same four parts. Before the loop, a rectangle sets the starting values. Then a diamond tests whether to go round again. Inside the loop, one or more rectangles do the work. Last, a rectangle moves the counter on, and its arrow goes back up to the diamond. The diamond's other answer is the way out.
Draw the back arrow up the side of the chart, into the side of the diamond, rather than through the steps it skips; the diagrams on this page are laid out that way automatically, and it is what a reader expects. And check the fourth part every time. A loop whose counter never changes never ends, and in a flowchart that is visible: there is no step between the diamond and the back arrow that could make the answer change.
Factorial: a loop that accumulates
The factorial of n, written n!, is the product of the whole numbers from 1 to n: 5! is 1 × 2 × 3 × 4 × 5, which is 120. The flowchart keeps a running product in fact, starting at 1, and multiplies it by i each time round while i counts up to n.
Pseudocode
START
READ n
fact ← 1
i ← 1
WHILE i ≤ n DO
fact ← fact × i
i ← i + 1
END WHILE
PRINT fact
ENDPython
n = int(input())
fact = 1
i = 1
while i <= n:
fact = fact * i
i = i + 1
print(fact)C
#include <stdio.h>
int main(void) {
int n;
scanf("%d", &n);
unsigned long long fact = 1; /* exact up to n = 20 */
for (int i = 1; i <= n; i++)
fact = fact * i;
printf("%llu\n", fact);
return 0;
}Three details decide whether the answer is right. fact starts at 1, not 0, because anything multiplied by 0 stays 0. The test is i ≤ n, not i < n, or the last multiplication never happens and 5 gives 24. And 0! is 1 by definition, which this chart gets right without a special case: with n = 0 the loop never runs and the starting value is printed.
The C version uses unsigned long long and says in a comment that it is exact up to n = 20. The C standard guarantees that type holds numbers up to at least 18,446,744,073,709,551,615 (264 − 1). 20! is 2,432,902,008,176,640,000 and fits; 21! is 51,090,942,171,709,440,000 and does not, so the C quietly gives a wrong answer from 21 on. Python's integers "have unlimited precision", in the words of its documentation, so the Python version is exact for any n. Saying which inputs your program handles correctly is part of a good answer.
Fibonacci: a loop that remembers two values
Each Fibonacci number is the sum of the two before it. Following the standard definition in the OEIS, the sequence starts from 0 and 1, so it runs 0, 1, 1, 2, 3, 5, 8. The loop needs two variables, a and b, holding the last two numbers, and prints a on each pass before moving both along.
Pseudocode
START
READ n
a ← 0
b ← 1
count ← 0
WHILE count < n DO
PRINT a
next ← a + b
a ← b
b ← next
count ← count + 1
END WHILE
ENDPython
n = int(input())
a, b = 0, 1
count = 0
while count < n:
print(a)
a, b = b, a + b
count = count + 1C
#include <stdio.h>
int main(void) {
int n;
scanf("%d", &n);
unsigned long long a = 0, b = 1; /* exact up to n = 94 */
for (int count = 0; count < n; count++) {
printf("%llu\n", a);
unsigned long long next = a + b;
a = b;
b = next;
}
return 0;
}The inputs each version handles
- Python
- Any n. Python's integers have no upper limit.
- C
- n up to 94. The last number printed is then 12,200,160,415,121,876,738, the largest Fibonacci number an unsigned long long is guaranteed to hold; from n = 95 the last number printed is wrong.
The step that moves the pair along is where the mistake usually is. Written as two separate assignments, a = b then b = a + b, the second line uses the new a, and the sequence goes wrong from the third number. The flowchart avoids it with a third variable, next, computed before either changes; Python can do the same in one line with a, b = b, a + b, which evaluates the right-hand side first. Some textbooks start the sequence at 1, 1 instead of 0, 1; if yours does, change the starting values and say so.
Prime test: a loop that can stop early
A whole number is prime if it is at least 2 and no number other than 1 and itself divides it. The chart first rejects anything below 2, since 0 and 1 are not prime. Then it tries divisors from 2 upwards, and the moment one divides n exactly, it has its answer and leaves the loop.
Pseudocode
START
READ n
IF n < 2 THEN
PRINT "Not prime"
STOP
END IF
i ← 2
WHILE i × i ≤ n DO
IF n MOD i = 0 THEN
PRINT "Not prime"
STOP
END IF
i ← i + 1
END WHILE
PRINT "Prime"
ENDPython
n = int(input())
prime = n >= 2
i = 2
while prime and i * i <= n:
if n % i == 0:
prime = False
i = i + 1
print("Prime" if prime else "Not prime")C
#include <stdio.h>
int main(void) {
int n;
scanf("%d", &n);
int prime = n >= 2;
for (int i = 2; prime && i <= n / i; i++)
if (n % i == 0)
prime = 0;
printf(prime ? "Prime\n" : "Not prime\n");
return 0;
}The inputs each version handles
- Python
- Any whole number.
- C
- n up to 2,147,483,647, the largest int where int is 32 bits. The loop tests i <= n / i rather than i * i <= n: for n above 2,147,395,600, i * i would overflow an int before the loop could stop.
The test in the loop is i × i ≤ n, not i < n, and it is worth explaining in an answer why that is enough. If n is the product of two numbers, the smaller of them can be at most the square root of n, so any divisor will have been found by the time i passes it. For 97 that is 8 tries (2 to 9) instead of 95. Writing i × i rather than a square root also keeps the arithmetic in whole numbers. The C version writes the same test as i <= n / i, which asks the same question without multiplying, so it cannot overflow when n is near the largest number an int holds.
The flowchart has two routes to "Not prime": the early rejection and the divisor found inside the loop. Both point at the same parallelogram, and that is tidier than drawing it twice. Common marks lost here are treating 1 as prime, and printing "Prime" inside the loop as soon as one divisor fails to divide, before the others have been tried.
The next page uses the same loop shape to walk along a list and a string.