More trace tables: nested loops, arrays and subroutines

A nested loop is a loop inside another loop.

The inner loop runs all the way through on every pass of the outer loop.

t = 0
for i = 1 to 2
    for j = 1 to 3
        t = t + j
    next j
next i
print(t)

t ← 0
FOR i ← 1 TO 2
    FOR j ← 1 TO 3
        t ← t + j
    ENDFOR
ENDFOR
OUTPUT t

t = 0
for i in range(1, 3):
    for j in range(1, 4):
        t = t + j
print(t)

Start a new row each time the inner loop runs once. i stays the same while j counts, then j starts again from 1 when i changes.

The program prints 12. The line inside both loops runs 2 × 3 = 6 times: the passes multiply, they do not add.

Working through a program by hand like this, without a computer, writing down each value as it changes, is called a dry run. The trace table is where you write the values.

To count how many times a loop runs, count the values its variable takes. for j = 1 to 3 gives j = 1, 2, 3: both ends are included, so 3 passes. for j = 0 to 10 step 5 makes j jump by 5 each time: j = 0, 5, 10, so 3 passes.

A nested loop with 4 passes outside and 3 inside runs its inner line 4 × 3 = 12 times.

An array is a list of items stored under one name, such as nums.

Each item has an index, its position number. Most loops over an array use the index as the loop variable.

Indexes start at 0, so the last index is the length minus 1. Asking for nums[nums.length] goes one place past the end, and the program stops with an error.

nums = [4, 9, 2, 7]
big = nums[0]
for i = 1 to nums.length - 1
    if nums[i] > big then
        big = nums[i]
    endif
next i
print(big)

nums ← [4, 9, 2, 7]
big ← nums[0]
FOR i ← 1 TO LEN(nums) - 1
    IF nums[i] > big THEN
        big ← nums[i]
    ENDIF
ENDFOR
OUTPUT big

nums = [4, 9, 2, 7]
big = nums[0]
for i in range(1, len(nums)):
    if nums[i] > big:
        big = nums[i]
print(big)

Give the item itself a column, nums[i], as well as i. It stops you mixing up the position with the value stored there.

big only changes when the if is true. When the condition is false, copy the old value down.

MOD gives the remainder after dividing: 17 MOD 5 = 2, because 17 = 3 × 5 + 2. (Python writes it as %.)

It is often used to test for even and odd numbers: n MOD 2 is 0 when n is even and 1 when n is odd. So if nums[i] MOD 2 == 1 then picks out the odd items.

A loop can change the array itself. nums[i] = nums[i] + 10 replaces the item at index i with a new value, so after the loop the array holds the changed values.

A while loop can have two conditions joined by AND: it keeps going only while both are true, and stops as soon as either one is false. while i >= 0 AND nums[i] > 15 stops when i drops below 0 or it reaches an item that is 15 or less.

When a program calls a function, it jumps into the function with the values it passes in, runs it, and comes back with the value the function returns.

function f(n)
    return n * 2 + 1
endfunction
t = 0
for i = 1 to 3
    r = f(i)
    t = t + r
next i
print(t)

SUBROUTINE f(n)
    RETURN n * 2 + 1
ENDSUBROUTINE
t ← 0
FOR i ← 1 TO 3
    r ← f(i)
    t ← t + r
ENDFOR
OUTPUT t

def f(n):
    return n * 2 + 1
t = 0
for i in range(1, 4):
    r = f(i)
    t = t + r
print(t)

1. Pass 1: i = 1, so f(1) returns 1 × 2 + 1 = 3, and t = 0 + 3 = 3.

A parameter is the name a function gives to a value passed into it: in f(n), n is the parameter, and the call f(2) makes n = 2. When one call sits inside another, such as g(f(4), 2), work out the inner call first: f(4) is worked out, and its answer becomes g's first value.

A variable made inside a function, or a parameter such as n, is local: it belongs to that call only. Changing it never changes a variable of the same name in the main program.

A program with a logic error runs, but gives the wrong answer.

Trace it with data where you already know the right answer, and look for the first row where a value is not what you expected.

nums = [12, 7, 10, 15]
count = 0
for i = 0 to nums.length - 1
    if nums[i] >= 10 then
        count = count + 1
    endif
next i
print(count)

nums ← [12, 7, 10, 15]
count ← 0
FOR i ← 0 TO LEN(nums) - 1
    IF nums[i] ≥ 10 THEN
        count ← count + 1
    ENDIF
ENDFOR
OUTPUT count

nums = [12, 7, 10, 15]
count = 0
for i in range(len(nums)):
    if nums[i] >= 10:
        count = count + 1
print(count)

The trace gives count = 1, 1, 2, 3, and the program prints 3. The right answer is 2 (12 and 15).

The row with i = 2 is the first one that goes wrong: nums[2] is 10, which is not greater than 10, but count went up. The comparison should be greater than, not greater than or equal to.

Test with a value that sits exactly on a boundary, like 10 here. That is where off-by-one bugs hide.