Difficulty: Intermediate | Prerequisites: Functions, loops, basic operations, lists
This covers the techniques that turn basic Python skills into proper problem-solving: recursion (functions that call themselves), binary search (finding items in sorted data efficiently), and classic mathematical algorithms (prime checking, GCD, Fibonacci, base conversion). These topics are where CS124 shifts from "can you write a loop" to "can you think algorithmically."
Recursion
A technique where a function calls itself to solve a smaller instance of the same problem. Every recursive function needs a base case (when to stop) and a recursive case (how to break the problem down). Think of it as solving a big problem by solving a slightly smaller version of itself, over and over, until you hit something trivially simple.
Base case
The condition under which a recursive function stops calling itself and returns a value directly. Without a base case, the function recurses forever and crashes.
Recursive case
The part of the function that calls itself with a smaller or simpler input, moving toward the base case.
Call stack
The internal data structure Python uses to track which functions are currently running. Each recursive call adds a new frame to the stack. When the base case is reached, frames are resolved in reverse order (last in, first out).
Stack overflow (RecursionError)
What happens when recursion goes too deep (Python's default limit is around 1,000 frames). This typically means the base case is missing or never reached.
Binary search
An efficient search algorithm for sorted sequences. It repeatedly halves the search space by comparing the target to the middle element. Time complexity is O(log n), compared to O(n) for a linear scan.
GCD (greatest common divisor)
The largest positive integer that divides two numbers without a remainder. Also called the highest common factor (HCF). The Euclidean algorithm computes it efficiently.
Euclidean algorithm
A method for finding the GCD: repeatedly replace the larger number with the remainder of dividing the larger by the smaller, until the remainder is 0. The last non-zero remainder is the GCD. In simple terms, keep dividing and taking remainders until nothing is left over.
Prime number
A positive integer greater than 1 whose only divisors are 1 and itself. 2 is the smallest prime and the only even prime.
Fibonacci sequence
A sequence where each number is the sum of the two preceding ones: 0, 1, 1, 2, 3, 5, 8, 13, ... Defined by F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2).
Time complexity (Big O)
A way to describe how the running time of an algorithm grows as the input size increases. O(n) means linear growth, O(n^2) means quadratic, O(log n) means logarithmic. At this level, you just need an intuition for which is faster.
A recursive function has two parts: a base case that returns a value directly, and a recursive case that calls the function itself with a smaller input.
Each call creates a new frame on the call stack. When the base case is hit, the frames unwind, each one using the return value from the call below it.
Example (factorial): factorial(4) calls factorial(3), which calls factorial(2), which calls factorial(1), which returns 1. Then the frames unwind: 1, 2, 6, 24.
Factorial
Base case: if n == 0: return 1
Recursive case: return n * factorial(n - 1)
Fibonacci (nth number)
Base cases: if n == 0: return 0 and if n == 1: return 1
Recursive case: return fibonacci(n - 1) + fibonacci(n - 2)
Warning: the naive recursive version is very slow (exponential time) because it recomputes the same values repeatedly. An iterative version with two running variables is much more efficient for practical use.
Reversing a string
Base case: if len(s) <= 1: return s
Recursive case: return reverse(s[1:]) + s[0]
Take the first character, put it at the end, and reverse the rest.
Summing all numbers in a list
Base case: if len(lst) == 0: return 0
Recursive case: return lst[0] + sum_list(lst[1:])
Requires a sorted list.
Set low = 0 and high = len(lst) - 1.
While low <= high: compute mid = (low + high) // 2. If lst[mid] == target, return mid. If lst[mid] < target, set low = mid + 1. Otherwise, set high = mid - 1.
If the loop ends without finding the target, the element is not in the list.
Time complexity: O(log n). Each iteration eliminates half the remaining elements.
A number n is prime if it is greater than 1 and has no divisors other than 1 and itself.
You only need to check divisors up to the square root of n. If no divisor is found by then, n is prime.
Special cases: 0 and 1 are not prime. 2 is prime. All other even numbers are not prime.
To print all primes from 1 to 100: loop through each number and apply the prime check.
gcd(a, b): if b == 0, return a. Otherwise, return gcd(b, a % b).
This works because the GCD of a and b is the same as the GCD of b and (a mod b).
Example: gcd(48, 18) becomes gcd(18, 12), then gcd(12, 6), then gcd(6, 0), returning 6.
Can be written iteratively with a while loop as well.
Repeatedly divide the number by 2, recording the remainder each time.
The binary representation is the remainders read in reverse order.
Example: 13 divided by 2 gives remainders 1, 0, 1, 1. Reversed: 1101.
In code, build a string by prepending str(n % 2) and then setting n = n // 2, looping while n > 0.
To print the first 15 terms iteratively: start with a = 0 and b = 1. In each iteration, print a, then update: a, b = b, a + b.
This avoids the exponential cost of the naive recursive approach.
Use nested loops: the outer loop runs from 1 to 10, the inner loop runs from 1 to 10, and you print i * j formatted in a grid.
Fibonacci recurrence
F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) for n >= 2.
Euclidean algorithm for GCD
gcd(a, b) = a if b == 0, otherwise gcd(b, a % b). Terminates because the remainder strictly decreases toward 0.
Prime check bound
Only test divisors from 2 up to and including the integer square root of n. In Python: int(n ** 0.5) + 1 as the upper bound for range(). If n has a factor larger than its square root, it must also have one smaller than it, so you would have found it already.
Decimal to binary
Repeatedly compute n % 2 (gives the next binary digit, right to left) and n = n // 2 (shifts the number right). Collect the remainders and reverse them, or prepend each one to build the result left to right.
Binary search halving
mid = (low + high) // 2. Each comparison eliminates roughly half the search space, giving O(log n) time.
The most common recursion mistake is forgetting the base case, or writing a base case that is never reached. This causes infinite recursion and a RecursionError.
Students sometimes think recursion is always better than iteration. For problems like Fibonacci, naive recursion is far slower than a simple loop because it recomputes the same sub-problems exponentially many times.
Binary search only works on sorted data. Applying it to an unsorted list produces incorrect results. If asked to search an unsorted list, use a linear scan.
1 is not a prime number. This trips people up. The smallest prime is 2.
When converting decimal to binary, students sometimes read the remainders in the wrong order (top to bottom instead of bottom to top). The first remainder computed is the least significant bit, not the most significant.
⚠️ Expect at least one recursion question. You will likely need to write a recursive function from scratch and trace its execution step by step.
⚠️ Binary search is a classic exam question. Be able to write it from memory and trace through an example showing how low, high, and mid change each iteration.
⚠️ Know the Euclidean algorithm well enough to compute a GCD by hand and to write the code (both recursive and iterative versions).
⚠️ Prime-checking questions often ask you to optimise: checking only up to the square root, skipping even numbers after 2. Demonstrate you understand why these optimisations work.
⚠️ The Fibonacci sequence may appear as both a recursion exercise and a "write the iterative version" exercise. Know both and be ready to explain why the iterative one is faster.
Fill in the blank: Every recursive function must have a ______ to prevent infinite recursion. (Answer: base case)
True or False: Binary search has O(n) time complexity. (Answer: False. It has O(log n) time complexity.)
Fill in the blank: gcd(12, 8) using the Euclidean algorithm: gcd(12, 8) becomes gcd(8, ____). (Answer: 4, because 12 % 8 = 4.)
True or False: 1 is a prime number. (Answer: False. The smallest prime is 2.)
Fill in the blank: The naive recursive Fibonacci function has ______ time complexity. (Answer: exponential, or O(2^n).)
Q: Write a recursive function to compute the nth Fibonacci number.
A: Base cases: return 0 if n == 0, return 1 if n == 1. Recursive case: return fib(n - 1) + fib(n - 2). Note that this is O(2^n); the iterative version with two running variables is much faster.
Q: Write a program that prints the Fibonacci sequence up to the 15th term.
A: Use an iterative approach. Start with a, b = 0, 1. Loop 15 times, printing a each time, then update with a, b = b, a + b.
Q: Write a Python function to check if a number is prime.
A: Return False if n < 2. Loop from 2 to int(n ** 0.5) + 1. If any value divides n evenly (n % i == 0), return False. If the loop finishes, return True.
Q: Write a program to print all prime numbers between 1 and 100.
A: Loop from 2 to 100. For each number, call your prime-checking function. Print it if it returns True.
Q: Implement a Python program to find the GCD of two numbers.
A: Recursive: def gcd(a, b): return a if b == 0 else gcd(b, a % b). Iterative: use a while loop, replacing a, b with b, a % b until b == 0, then return a.
Q: Implement a binary search algorithm in Python.
A: Set low = 0, high = len(lst) - 1. While low <= high: compute mid = (low + high) // 2. If lst[mid] == target, return mid. If lst[mid] < target, set low = mid + 1. Otherwise, high = mid - 1. Return -1 if not found.
Q: Write a recursive function to reverse a string.
A: Base case: if len(s) <= 1: return s. Recursive case: return reverse(s[1:]) + s[0]. Each call peels off the first character and appends it at the end.
Q: Write a recursive function that sums all numbers in a list.
A: Base case: if len(lst) == 0: return 0. Recursive case: return lst[0] + sum_list(lst[1:]). Each call processes the first element and recurses on the rest.
Q: Write a program that converts a decimal number to binary without using bin().
A: Build the result string by repeatedly computing n % 2 (prepend to the string) and n = n // 2. Loop while n > 0. Handle the special case of n == 0 (binary is '0').
Q: Implement a Python program to print a multiplication table for numbers 1 to 10.
A: Use two nested for loops, both running range(1, 11). Print i * j formatted with spacing (e.g. f'{i * j:4}') to align the columns.
Q: Create a function that counts how many words are in a given sentence.
A: return len(sentence.split()). The split() method with no arguments splits on any whitespace and ignores leading/trailing spaces.
Q: Write a Python function that finds the index of the first occurrence of an element in a list.
A: Loop with for i in range(len(lst)):. If lst[i] == target, return i. If the loop ends without finding it, return -1 (or None).
Recursion is the conceptual foundation for divide-and-conquer algorithms like merge sort and quicksort, which appear in later CS courses. The call stack model reappears when studying scope, closures, and debugging.
Binary search is a specific case of the broader "reduce the search space" strategy. The same halving logic shows up in algorithms for root-finding, optimisation, and database indexing.
The Euclidean algorithm connects to number theory and cryptography (it is part of computing modular inverses, which underpin RSA encryption). Prime checking connects to the same domain.
Python recursion, base case, recursive case, call stack, stack overflow, RecursionError, binary search, sorted list search, logarithmic time, O(log n), GCD, greatest common divisor, Euclidean algorithm, prime number, prime check, sieve of Eratosthenes, Fibonacci sequence, iterative Fibonacci, recursive Fibonacci, decimal to binary, base conversion, multiplication table, nested loops, word count, linear search, first occurrence, CS124, UIUC, Intro to Computer Science I, Python algorithms