Programming Constructs

1. Variables and Data Types

Variables

A variable is a named storage location in memory that holds a value which can change during Program execution.

Primitive Data Types

Constants

A constant is a named value that cannot be changed after initialisation.

MAX_SIZE = 100
PI = 3.14159265

Type Casting

Converting a value from one type to another:

x = int(3.7)       # x = 3 (truncation)
y = float(5)       # y = 5.0
z = str(42)        # z = "42"

:::caution Pitfall In Python, int(3.9) truncates toward zero (gives 3), not rounds. Use round(3.9) for rounding. :::

2. Selection (Conditional Statements)

If-Else

if condition:
    statement_block
elif another_condition:
    alternative_block
else:
    default_block

Nested Selection

Selection statements can be nested, but excessive nesting reduces readability. Use guard clauses or Early returns where possible.

def classify_grade(score):
    if score < 0 or score > 100:
        return "Invalid"
    if score >= 70:
        return "A"
    if score >= 60:
        return "B"
    if score >= 50:
        return "C"
    return "Fail"

Case/Switch Statements

Some languages (not Python without match/case in 3.10+) provide switch statements for multi-way Branching.

3. Iteration

Definite Iteration (For Loop)

Executes a fixed number of times.

for i in range(n):
    print(i)

Invariant for for i in range(n): At the start of iteration $i$The loop body has executed Exactly $i$ times.

Indefinite Iteration (While Loop)

Executes until a condition becomes false.

while condition:
    statement_block

Loop Invariants

A loop invariant is a property that holds before and after each iteration.

Example: Sum of first $n$ natural numbers.

def sum_n(n):
    total = 0
    i = 1
    while i <= n:
        total += i
        i += 1
    return total

Invariant: At the start of each iteration, total = 1 + 2 + ... + (i - 1).

Proof:

• Init: Before the first iteration, $i = 1$total = 0. Sum of empty set = 0. ✓
• Maintenance: total increases by $i$Then $i$ increases by 1. After: total = 1 + ... + i and next $i' = i + 1$So invariant holds.
• Termination: $i = n + 1$. total = 1 + 2 + ... + n = n(n+1)/2. ✓

Do-While / Repeat-Until

Executes the body at least once, then checks the condition. Python does not have a native do-while; Emulate with:

while True:
    statement_block
    if not condition:
        break

:::info Board-specific AQA uses specific pseudocode format with IF ... THEN ... ELSE ... ENDIF And WHILE ... ENDWHILE. CIE (9618) uses its own pseudocode format; requires procedure and Function definitions with parameters. OCR (A) uses OCR-specific pseudocode format; requires Local and global variable scope understanding. Edexcel uses pseudocode similar to Python-style; Requires subroutines with parameters. :::

4. Recursion

Definition

A recursive function is one that calls itself. Every recursive function must have:

1. Base case(s): Direct answer(s) for the simplest input(s)
2. Recursive case: Reduce the problem and call itself on the smaller input

Example: Factorial

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

Correctness Proof by Induction

Theorem. factorial(n) returns $n!$ for all $n \geq 0$.

Proof. By induction on $n$.

Base case. $n = 0$: returns 1 = $0!$. ✓

Inductive step. Assume factorial(k) = k! for all $k \leq n$. Then:

$\mathrm{factorial}(n+1) = (n+1) \times \mathrm{factorial}(n) = (n+1) \times n! = (n+1)!$

✓ $\square$

Termination Proof

Theorem. factorial(n) terminates for all $n \geq 0$.

Proof. Define a variant function $V(n) = n$. Each recursive call decreases $V$ by 1: $V(n-1) = n - 1 \lt n = V(n)$. $V$ is a non-negative integer that strictly decreases. By the Well-ordering principle, $V$ must eventually reach a base case ($V = 0$ or $V = 1$). Therefore, the Recursion terminates. $\square$

Example: Fibonacci

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Complexity: $T(n) = T(n-1) + T(n-2) + O(1)$. This gives $T(n) = \Theta(\phi^n)$ where $\phi = \frac◆LB◆1+\sqrt{5}◆RB◆◆LB◆2◆RB◆ \approx 1.618$ (the golden ratio).

Proof sketch. The recurrence has characteristic equation $r^2 = r + 1$Giving roots $\phi$ and $\psi = \frac◆LB◆1-\sqrt{5}◆RB◆◆LB◆2◆RB◆$. The solution is $T(n) = A\phi^n + B\psi^n$. Since $|\psi| \lt 1$ $T(n) = \Theta(\phi^n)$. $\square$

:::caution Warning Iteration for $O(n)$ time:

def fib_iter(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

Example: Tower of Hanoi

def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    hanoi(n - 1, source, auxiliary, target)
    print(f"Move disk {n} from {source} to {target}")
    hanoi(n - 1, auxiliary, target, source)

Complexity: $T(n) = 2T(n-1) + O(1) \implies T(n) = \Theta(2^n)$.

Proof. $T(n) = 2T(n-1) + 1 = 2(2T(n-2)+1)+1 = 4T(n-2)+3 = \cdots = 2^n T(0) + (2^n - 1) = \Theta(2^n)$. Minimum moves = $2^n - 1$. $\square$

5. Procedures and Functions

Procedures vs Functions

def print_report(data):    # Procedure
    for item in data:
        print(item)

def calculate_average(data):  # Function
    return sum(data) / len(data)

Parameters

• By value: A copy of the argument is passed. Changes inside the function do not affect the original. (Default in Python for immutable types.)
• By reference: A reference to the original is passed. Changes affect the original. (Python passes object references; mutable objects like lists can be modified.)

def modify_list(lst):
    lst.append(4)    # Modifies the original list (by reference)
    lst = [0]        # Only rebinds the local variable (no effect outside)

my_list = [1, 2, 3]
modify_list(my_list)
print(my_list)  # [1, 2, 3, 4]

Problem Set

Problem 1. Write a recursive function to compute the sum of digits of a positive integer. Prove Its correctness by induction.

def sum_digits(n):
    if n < 10:
        return n
    return n % 10 + sum_digits(n // 10)

Problem 2. Convert the following while loop to a for loop:

i = 5
while i <= 50:
    print(i)
    i += 5

for i in range(5, 51, 5):
    print(i)

Problem 3. Prove that the following function computes $2^n$:

def power_of_two(n):
    if n == 0:
        return 1
    return 2 * power_of_two(n - 1)

Problem 4. Explain the difference between iteration and recursion. When would you prefer one Over the other?

Problem 5. Write a function that uses recursion to check if a string is a palindrome. Prove Termination.

def is_palindrome(s):
    if len(s) <= 1:
        return True
    if s[0] != s[-1]:
        return False
    return is_palindrome(s[1:-1])

Problem 6. What is the output of the following code? Explain step by step.

x = 10
def modify(x):
    x = 20
modify(x)
print(x)

Problem 7. Write a function gcd(a, b) using Euclid’s algorithm. Prove it terminates and Returns the GCD.

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

Problem 8. A student writes the following recursive function. Identify the bug and fix it:

def countdown(n):
    print(n)
    countdown(n - 1)

def countdown(n):
    if n < 0:
        return
    print(n)
    countdown(n - 1)

def countdown(n):
    while n >= 0:
        print(n)
        n -= 1

For revision on data structures that use recursion, see Trees.

6. Worked Examples: Nested Loops and Input Validation

Worked Example: Nested Loop Trace

Trace the execution of the following code and determine the output:

for i in range(1, 4):
    for j in range(1, i + 1):
        print("*", end="")
    print()

Trace:

Output:

*
**
***

Worked Example: Input Validation Loop

Write a function that repeatedly asks the user for an integer between 1 and 100 (inclusive) until Valid input is provided.

def get_valid_score():
    while True:
        try:
            score = int(input("Enter a score (1-100): "))
            if 1 <= score <= 100:
                return score
            print("Score must be between 1 and 100.")
        except ValueError:
            print("Invalid input. Please enter an integer.")

This loop combines two validation checks: type validation (integer) and range validation (1-100). The loop only exits when both checks pass.

Worked Example: Nested Loop — Multiplication Table

def multiplication_table(n):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            print(f"{i * j:4}", end="")
        print()

multiplication_table(5)

Output:

   1   2   3   4   5
   2   4   6   8  10
   3   6   9  12  15
   4   8  12  16  20
   5  10  15  20  25

7. Recursion Trace Walkthrough

Trace: Factorial of 4

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

Call: factorial(4)

factorial(4)
├── 4 * factorial(3)
│   ├── 3 * factorial(2)
│   │   ├── 2 * factorial(1)
│   │   │   └── returns 1
│   │   └── returns 2 * 1 = 2
│   └── returns 3 * 2 = 6
└── returns 4 * 6 = 24

Stack at deepest point (4 frames):

Trace: Fibonacci of 5

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Call: fib(5)

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1) → 1
│   │   │   └── fib(0) → 0
│   │   │   returns 1
│   │   └── fib(1) → 1
│   │   returns 2
│   └── fib(2)
│       ├── fib(1) → 1
│       └── fib(0) → 0
│       returns 1
│   returns 3
└── fib(3)
    ├── fib(2) → 1
    └── fib(1) → 1
    returns 2
returns 5

Note: fib(3) is computed twice, fib(2) is computed three times. This redundancy is why naive Recursive Fibonacci is $O(\phi^n)$ — it recomputes the same subproblems repeatedly.

8. Common Pitfalls

Off-by-One Errors

Off-by-one errors occur when a loop iterates one time too many or one time too few.

Infinite Loops

An infinite loop occurs when the loop condition never becomes false.

# Bug: x never changes
x = 0
while x < 10:
    print(x)

# Bug: wrong increment direction
x = 10
while x > 0:
    x = x + 1  # x increases, never reaches 0

# Bug: floating point comparison
x = 0.0
while x != 1.0:
    x += 0.1  # May never exactly equal 1.0 due to rounding

Fix for floating point: Use a tolerance or integer counter:

for i in range(10):
    x = i * 0.1

Scope Issues

Understanding variable scope is critical for correct programs.

# Pitfall: modifying a global variable
count = 0

def increment():
    count = count + 1  # UnboundLocalError!
    # This creates a local 'count' shadowing the global

def increment_fixed():
    global count
    count = count + 1  # Correct: references the global variable

# Pitfall: mutable default arguments
def add_item(item, items=[]):
    items.append(item)
    return items

print(add_item(1))  # [1]
print(add_item(2))  # [1, 2] — NOT [2]!

The default list [] is created once when the function is defined, not each time it is called. Fix:

def add_item(item, items=None):
    if items is None:
        items = []
    items.append(item)
    return items

9. Additional Problem Set

Problem 1. Trace the following code and state the output:

result = 0
for i in range(3):
    for j in range(3):
        if i == j:
            result += 1
        elif i > j:
            result += 2
        else:
            result += 3
print(result)

Problem 2. Write a recursive function binary_search(arr, target, low, high) that returns the Index of target in a sorted array, or -1 if not found. Prove that it terminates.

def binary_search(arr, target, low, high):
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return binary_search(arr, target, low, mid - 1)
    else:
        return binary_search(arr, target, mid + 1, high)

Problem 3. The following function is intended to compute the sum of all even numbers from 1 to n. Find and fix the bug.

def sum_even(n):
    total = 0
    for i in range(1, n):
        if i % 2 == 0:
            total += i
    return total

def sum_even(n):
    total = 0
    for i in range(1, n + 1):
        if i % 2 == 0:
            total += i
    return total

def sum_even(n):
    total = 0
    for i in range(2, n + 1, 2):
        total += i
    return total

Problem 4. Write a function validate_password(password) that returns True if the password Meets all of the following rules, and False otherwise:

• At least 8 characters long
• Contains at least one uppercase letter
• Contains at least one digit
• Contains at least one special character from !@#$%^&*

def validate_password(password):
    if len(password) < 8:
        return False
    has_upper = False
    has_digit = False
    has_special = False
    specials = set("!@#$%^&*")
    for char in password:
        if char.isupper():
            has_upper = True
        elif char.isdigit():
            has_digit = True
        elif char in specials:
            has_special = True
    return has_upper and has_digit and has_special

def validate_password(password):
    if len(password) < 8:
        return False
    has_upper = any(c.isupper() for c in password)
    has_digit = any(c.isdigit() for c in password)
    has_special = any(c in "!@#$%^&*" for c in password)
    return has_upper and has_digit and has_special

Problem 5. Explain the output of the following code. Why does the second call behave Unexpectedly?

def append_to(element, target=[]):
    target.append(element)
    return target

print(append_to(1))
print(append_to(2))

[1]
[1, 2]

def append_to(element, target=None):
    if target is None:
        target = []
    target.append(element)
    return target

Summary

This topic covers the core concepts of programming constructs, including underlying theory, practical implementation, and key applications.

Key concepts include:

• variables, data types, and control flow
• functions and procedures
• object-oriented programming
• error handling and debugging
• modular design

Understanding these concepts thoroughly is essential for both examinations and practical programming, and requires both theoretical knowledge and hands-on practice.

:::