Skip to main content

Basic Programming Concepts

TL;DR​

Variables store data with a type and scope. Control flow structures (if/else, loops) direct program execution. Functions encapsulate logic and enable recursion for problems decomposable into subproblems. Iteration repeats logic over collections. Understanding these fundamentals is essential for algorithm development.

Core Concepts​

Variables and Data Types​

Variables are named storage locations that hold values. Each variable has a type (integer, string, boolean, etc.) that determines what values it can store and what operations are allowed.

Key characteristics:

  • Name: Identifier for accessing the variable
  • Type: Determines memory allocation and valid operations
  • Scope: Defines where the variable is accessible (local, global)
  • Lifetime: How long the variable exists in memory
  • Value: The actual data stored

Scope matters in algorithms—global variables can lead to unexpected state changes, while local variables keep logic isolated and testable.

Control Flow Structures​

Control flow determines the order in which statements execute:

Conditional statements (if/else, switch):

  • Execute different code blocks based on conditions
  • Enable decision-making logic
  • Can be nested for complex branching

Loops execute code repeatedly:

  • While loops: Continue while condition is true
  • For loops: Iterate a fixed number of times
  • Do-while loops: Execute at least once, then check condition

Functions and Abstraction​

Functions are reusable blocks of code that accept inputs (parameters) and return outputs. Functions enable:

  • Code reuse: Write once, call many times
  • Abstraction: Hide complexity behind simple interfaces
  • Modularity: Break problems into smaller pieces
  • Testability: Test each function independently

Function signatures define parameters, return types, and behavior contracts. Parameters can be passed by value (copy) or reference (pointer), affecting performance in algorithms.

Recursion​

Recursion occurs when a function calls itself to solve smaller instances of the same problem. Every recursive solution requires:

Base case: The simplest instance that returns directly without recursion Recursive case: The function calls itself with a simpler problem

Example: Factorial(n) = n * Factorial(n-1) when n > 1; returns 1 when n = 1.

Recursion enables elegant solutions for:

  • Tree/graph traversals
  • Divide-and-conquer algorithms
  • Backtracking problems
  • Natural problem decomposition

Each recursive call uses stack memory. Deep recursion causes stack overflow; iterative solutions may be more efficient.

Iteration Patterns​

Iteration repeats logic over data collections or for fixed counts:

Index-based iteration: Loop through array indices, access elements Element-based iteration: Loop directly over values (foreach/for-in) While loops: Iterate while condition holds true

Understanding iteration is crucial for:

  • Traversing data structures
  • Searching and sorting
  • Processing collections efficiently
  • Building algorithms with predictable performance

Key Algorithms and Techniques​

Iterate through elements sequentially to find a target. O(n) time complexity, useful for unsorted data.

Factorial Recursion​

Classic recursive example: multiply n by factorial of n-1.

Nested Loops​

Process multi-dimensional data or find pairs: O(n²) time when iterating through all pairs.

Loop Unrolling​

Process multiple elements per iteration to reduce loop overhead (performance optimization).

Practical Example​

# Variables and basic control flow
age = 25
name = "Alice"
is_student = True

if age >= 18:
    print(f"{name} is an adult")
else:
    print(f"{name} is a minor")

# Function definition
def fibonacci(n):
    """Recursive function to compute nth Fibonacci number"""
    if n <= 1:
        return n  # Base case
    return fibonacci(n - 1) + fibonacci(n - 2)  # Recursive case

# Iteration patterns
numbers = [1, 2, 3, 4, 5]

# Index-based iteration
for i in range(len(numbers)):
    print(f"Index {i}: {numbers[i]}")

# Element-based iteration
for num in numbers:
    print(f"Value: {num}")

# While loop
i = 0
while i < len(numbers):
    print(numbers[i])
    i += 1

# Result
print(f"Fibonacci(6) = {fibonacci(6)}")  # Output: 8

Common Pitfalls​

warning

Infinite loops: Forgetting to update loop condition or missing break statement causes program to hang. Always verify loop termination conditions.

Stack overflow from deep recursion: Deeply recursive functions exhaust stack memory. Consider iterative solutions or tail recursion optimization.

Off-by-one errors: Loop boundaries (i < n vs i <= n) and array indexing cause common bugs. Carefully verify loop ranges.

Scope confusion: Variables with same name in different scopes cause subtle bugs. Use descriptive names and understand variable lifetime.

Type mismatches: Assigning wrong types to variables causes runtime errors or unexpected behavior. Use type checking and explicit conversions.

Advanced Control Flow Patterns​

Pattern 1: Early Exit​

def find_user(users, target_id):
    for user in users:
        if user.id == target_id:
            return user  # Early exit
    return None  # Not found

Early exit is more efficient than collecting all matches.

Pattern 2: Nested Loops with Break​

def find_pair_with_sum(numbers, target):
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):
            if numbers[i] + numbers[j] == target:
                return (i, j)  # Found pair
            # Could also use `break` on inner loop only
    return None

Pattern 3: Recursion with Memoization​

memo = {}

def fibonacci_fast(n):
    if n in memo:
        return memo[n]  # Cache hit

    if n <= 1:
        return n

    result = fibonacci_fast(n-1) + fibonacci_fast(n-2)
    memo[n] = result
    return result

Memoization transforms exponential recursion (2^n) into linear (n).

Scope and Lifetime Examples​

Variable Scope Issues​

x = 10  # Global scope

def modify_global():
    global x  # Must declare to modify global
    x = 20

def local_scope():
    x = 30  # Local x shadows global x
    return x  # Returns 30, global x unchanged

modify_global()
print(x)  # 20 - global was modified

print(local_scope())  # 30 - local x
print(x)  # Still 20 - local x didn't affect global

Parameter Passing: Value vs. Reference​

Pass by Value (copy):

def modify_value(x):
    x = x + 1
    return x

a = 5
result = modify_value(a)
# a is still 5 (was copied, not modified)

Pass by Reference (object reference):

def modify_list(lst):
    lst.append(99)  # Modifies original list

numbers = [1, 2, 3]
modify_list(numbers)
# numbers is now [1, 2, 3, 99] (object was modified)

In Python, primitives are pass-by-value, objects are pass-by-reference.

Time Complexity Examples​

# O(1) - Constant time
def get_first(lst):
    return lst[0]

# O(n) - Linear time
def find_max(lst):
    max_val = lst[0]
    for num in lst[1:]:
        if num > max_val:
            max_val = num
    return max_val

# O(n²) - Quadratic time
def bubble_sort(lst):
    n = len(lst)
    for i in range(n):
        for j in range(n - i - 1):
            if lst[j] > lst[j+1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]
    return lst

# O(log n) - Logarithmic time (binary search)
def binary_search(lst, target):
    left, right = 0, len(lst) - 1
    while left <= right:
        mid = (left + right) // 2
        if lst[mid] == target:
            return mid
        elif lst[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Testing Algorithms​

def test_factorial():
    assert factorial(0) == 1  # Edge case
    assert factorial(1) == 1  # Edge case
    assert factorial(5) == 120
    assert factorial(10) == 3628800

def test_fibonacci():
    assert fibonacci(0) == 0  # Edge case
    assert fibonacci(1) == 1  # Edge case
    assert fibonacci(6) == 8
    assert fibonacci(10) == 55

def test_binary_search():
    sorted_list = [1, 3, 5, 7, 9, 11]
    assert binary_search(sorted_list, 7) == 3
    assert binary_search(sorted_list, 1) == 0
    assert binary_search(sorted_list, 11) == 5
    assert binary_search(sorted_list, 8) == -1  # Not found

    # Edge cases
    assert binary_search([], 5) == -1  # Empty list
    assert binary_search([5], 5) == 0  # Single element
    assert binary_search([1], 2) == -1  # Single element, not found

def test_linear_search():
    numbers = [5, 2, 8, 1, 9]
    assert linear_search(numbers, 8) == 2
    assert linear_search(numbers, 1) == 3
    assert linear_search(numbers, 99) == -1  # Not found

Always test edge cases: n=0, n=1, duplicates, boundary values, empty inputs, single elements.

Algorithm Complexity Analysis​

Measuring Performance​

import time

def measure_time(func, *args):
    start = time.perf_counter()
    result = func(*args)
    end = time.perf_counter()
    return result, (end - start) * 1000  # milliseconds

# Linear search on list of 1M elements
arr = list(range(1_000_000))
result, time_ms = measure_time(linear_search, arr, 999_999)
print(f"Linear search: {time_ms:.2f}ms")  # ~50ms for last element

# Binary search on same list
result, time_ms = measure_time(binary_search, arr, 999_999)
print(f"Binary search: {time_ms:.2f}ms")  # ~0.05ms (1000x faster!)

Complexity is crucial: doubling input size should double linear O(n) time, but barely affect binary O(log n) search.

Scope and Lifetime Deep Dive​

# Global scope
global_var = 100

def outer():
    outer_var = 50  # Outer function scope

    def inner():
        inner_var = 25  # Inner function scope

        # Can access all scopes
        print(global_var)  # 100
        print(outer_var)   # 50
        print(inner_var)   # 25

        # Modify outer scope (with nonlocal keyword)
        nonlocal outer_var
        outer_var = 60

    return inner

func = outer()
func()  # Prints 100, 50, 25 and modifies outer_var

Scope rules: Local (function) → Enclosing (nested function) → Global → Built-in.

Sorting Algorithms Explained​

Bubble Sort​

def bubble_sort(arr):
    """Bubble sort: O(n²) time, O(1) space"""
    n = len(arr)

    for i in range(n):
        swapped = False
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True

        if not swapped:
            break  # Already sorted

    return arr

# Example: [3, 1, 4, 1, 5]
# Pass 1: [1, 3, 1, 4, 5]
# Pass 2: [1, 1, 3, 4, 5]
# Sorted!

Quicksort (Divide-and-Conquer)​

def quicksort(arr):
    """Quicksort: O(n log n) average, O(n²) worst case"""
    if len(arr) <= 1:
        return arr

    # Pick pivot (middle element)
    pivot = arr[len(arr) // 2]

    # Partition into three parts
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    # Recursively sort left and right
    return quicksort(left) + middle + quicksort(right)

# Divide-and-conquer: breaks problem into smaller subproblems

Self-Check​

  1. What is the difference between a function parameter passed by value versus by reference, and how does this affect algorithm efficiency? (Value = copy; Reference = pointer; reference is faster for large objects)

  2. Explain the base case and recursive case for the factorial function. Why are both necessary? (Base case stops recursion; recursive case breaks problem into smaller pieces. Without base case, infinite recursion. Without recursive case, can't solve larger problem)

  3. When would you use a while loop instead of a for loop in an algorithm? (When iteration count is unknown, when condition is complex, when you need manual counter control)

  4. What's the time complexity of the fibonacci recursive function without memoization? (O(2^n), exponential—each call spawns two more calls)

  5. How does memoization improve algorithm performance? (Caches results, so duplicate computations are O(1) lookups instead of recomputing)

One Takeaway​

info

Master these foundational concepts—variables, control flow, functions, recursion, and iteration—and you'll have the building blocks for any algorithm. Clean code with clear variable names, proper scoping, and well-structured functions makes algorithms easier to understand, test, and optimize. Practice writing simple, clean implementations before optimizing for performance.

References​

  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
  • McDowell, G. L. (2015). Cracking the Coding Interview (6th ed.). CareerCup.
  • Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.
  • Bhargava, A. Y. (2016). Grokking Algorithms: An Illustrated Guide for Programmers and Other Curious People. Manning.
  • Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.). Addison-Wesley.