1. Problems 41–50
Same format as the previous modules: expand a problem to see the approach and both commented solutions.
Problems 41 and 42 are recursive rewrites of the iterative factorial and Fibonacci from Module 2. They read more directly like the mathematical definition, but each recursive call adds a stack frame — the recursive Fibonacci in particular recomputes the same values repeatedly and is exponential in time, where the iterative version is linear. Prefer iteration once performance matters; reach for recursion when it makes the logic clearer.
P41
Factorial via Recursion
6! = 6 × 5! — the recursive definition, written directly.
Factorial via Recursion
6! = 6 × 5! — the recursive definition, written directly.
Approach: a base case (n ≤ 1 returns 1) stops the recursion; every other call returns n times the factorial of n - 1, letting the language's call stack do the work Module 2's loop did by hand.
JavaScript
function factorialRecursive(n) {
if (n <= 1) return 1; // base case
return n * factorialRecursive(n - 1); // n! = n * (n-1)!
}
console.log(factorialRecursive(6)); // 720Python
def factorial_recursive(n: int) -> int:
if n <= 1: # base case
return 1
return n * factorial_recursive(n - 1) # n! = n * (n-1)!
print(factorial_recursive(6)) # 720
P42
Fibonacci via Recursion
fib(10) = 55 — the same answer as Module 2, a different-shaped solution.
Fibonacci via Recursion
fib(10) = 55 — the same answer as Module 2, a different-shaped solution.
Approach: two base cases (fib(0) = 0, fib(1) = 1), and every other call returns the sum of the two calls before it — a direct translation of the definition, at the cost of recomputing smaller values many times over.
JavaScript
function fibonacciRecursive(n) {
if (n <= 1) return n; // base cases
return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}
console.log(fibonacciRecursive(10)); // 55Python
def fibonacci_recursive(n: int) -> int:
if n <= 1: # base cases
return n
return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
print(fibonacci_recursive(10)) # 55
P43
Sum of a List via Recursion
[1,2,3,4,5] → 15, built from "first element + sum of the rest."
Sum of a List via Recursion
[1,2,3,4,5] → 15, built from "first element + sum of the rest."
Approach: an empty list sums to 0 (base case); otherwise the sum is the first element plus the recursive sum of everything after it — the list itself shrinks by one element on every call, which is what guarantees the recursion ends.
JavaScript
function sumRecursive(arr) {
if (arr.length === 0) return 0; // base case: an empty list sums to 0
return arr[0] + sumRecursive(arr.slice(1)); // first element + sum of the rest
}
console.log(sumRecursive([1, 2, 3, 4, 5])); // 15Python
def sum_recursive(items: list) -> int:
if len(items) == 0: # base case: an empty list sums to 0
return 0
return items[0] + sum_recursive(items[1:]) # first element + sum of the rest
print(sum_recursive([1, 2, 3, 4, 5])) # 15
P44
Binary Search
Find 7 in [1,3,5,7,9,11] in O(log n) instead of scanning every element.
Binary Search
Find 7 in [1,3,5,7,9,11] in O(log n) instead of scanning every element.
Approach: only works on a sorted list. Check the middle element: if it's the target, done; if the target is bigger, the whole left half can be discarded; if smaller, discard the right half. Repeat on the remaining half until found or the search space is empty.
JavaScript
function binarySearch(sortedArr, target) {
let low = 0;
let high = sortedArr.length - 1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (sortedArr[mid] === target) return mid; // found it
if (sortedArr[mid] < target) low = mid + 1; // search the right half
else high = mid - 1; // search the left half
}
return -1; // not found
}
console.log(binarySearch([1, 3, 5, 7, 9, 11], 7)); // 3Python
def binary_search(sorted_items: list, target) -> int:
low, high = 0, len(sorted_items) - 1
while low <= high:
mid = (low + high) // 2
if sorted_items[mid] == target: # found it
return mid
if sorted_items[mid] < target:
low = mid + 1 # search the right half
else:
high = mid - 1 # search the left half
return -1 # not found
print(binary_search([1, 3, 5, 7, 9, 11], 7)) # 3
P45
Linear Search
Find 9 in [4,2,9,6] by checking each element in order.
Linear Search
Find 9 in [4,2,9,6] by checking each element in order.
Approach: no sorting required — check every element in order and return its index the moment it matches. Worth contrasting directly against binary search: this is O(n), simple, and works on any list.
JavaScript
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i; // index of the first match
}
return -1; // not found
}
console.log(linearSearch([4, 2, 9, 6], 9)); // 2Python
def linear_search(items: list, target) -> int:
for i in range(len(items)):
if items[i] == target: # index of the first match
return i
return -1 # not found
print(linear_search([4, 2, 9, 6], 9)) # 2
P46
Function With a Variable Number of Arguments
sumAll(1,2,3) and sumAll(10,20,30,40) both need to work — same function.
Function With a Variable Number of Arguments
sumAll(1,2,3) and sumAll(10,20,30,40) both need to work — same function.
Approach: JavaScript's rest parameter (...numbers) and Python's *args both do the same job — they collect however many positional arguments were passed into a single array/tuple you can loop over normally.
JavaScript
function sumAll(...numbers) { // rest parameter collects every argument into an array
let total = 0;
for (const num of numbers) {
total += num;
}
return total;
}
console.log(sumAll(1, 2, 3)); // 6
console.log(sumAll(10, 20, 30, 40)); // 100Python
def sum_all(*numbers) -> int: # *args collects every argument into a tuple
total = 0
for num in numbers:
total += num
return total
print(sum_all(1, 2, 3)) # 6
print(sum_all(10, 20, 30, 40)) # 100
P47
Swap Two Variables Without a Temp Variable
swap(5, 9) → (9, 5), with no third variable involved.
Swap Two Variables Without a Temp Variable
swap(5, 9) → (9, 5), with no third variable involved.
Approach: both languages can assign to multiple variables from a single right-hand-side expression in one step — array destructuring in JavaScript, tuple unpacking in Python — so the swap happens simultaneously instead of needing a holding variable.
JavaScript
function swap(a, b) {
[a, b] = [b, a]; // array destructuring swaps both sides in one step
return [a, b];
}
console.log(swap(5, 9)); // [9, 5]Python
def swap(a, b):
a, b = b, a # tuple assignment swaps both sides in one step
return a, b
print(swap(5, 9)) # (9, 5)
P48
Balanced Parentheses Check
"{[()()]}" is balanced; "{[(])}" isn't — brackets close in the wrong order.
Balanced Parentheses Check
"{[()()]}" is balanced; "{[(])}" isn't — brackets close in the wrong order.
Approach: a stack. Every opening bracket gets pushed on; every closing bracket must match whatever was most recently pushed (popped off the top) — if it doesn't match, or the stack is empty when a closer arrives, the expression is unbalanced. At the very end, the stack must be empty too.
JavaScript
function isBalanced(expr) {
const stack = [];
const pairs = { ")": "(", "]": "[", "}": "{" };
for (const ch of expr) {
if (ch === "(" || ch === "[" || ch === "{") {
stack.push(ch); // opening bracket: remember it
} else if (ch === ")" || ch === "]" || ch === "}") {
if (stack.pop() !== pairs[ch]) return false; // wrong or missing opener
}
}
return stack.length === 0; // every opener must have been closed
}
console.log(isBalanced("{[()()]}")); // true
console.log(isBalanced("{[(])}")); // falsePython
def is_balanced(expr: str) -> bool:
stack = []
pairs = {")": "(", "]": "[", "}": "{"}
for ch in expr:
if ch in "([{":
stack.append(ch) # opening bracket: remember it
elif ch in ")]}":
if not stack or stack.pop() != pairs[ch]: # wrong or missing opener
return False
return len(stack) == 0 # every opener must have been closed
print(is_balanced("{[()()]}")) # True
print(is_balanced("{[(])}")) # False
P49
Decimal to Binary Conversion
13 in binary is "1101".
Decimal to Binary Conversion
13 in binary is "1101".
Approach: repeatedly divide the number by 2, recording the remainder (0 or 1) each time. The remainders come out least-significant-bit first, so each new bit is prepended to the front of the result rather than appended.
JavaScript
function toBinary(n) {
if (n === 0) return "0";
let bits = "";
n = Math.abs(n);
while (n > 0) {
bits = (n % 2) + bits; // prepend each remainder, right to left
n = Math.floor(n / 2);
}
return bits;
}
console.log(toBinary(13)); // "1101"Python
def to_binary(n: int) -> str:
if n == 0:
return "0"
bits = ""
n = abs(n)
while n > 0:
bits = str(n % 2) + bits # prepend each remainder, right to left
n //= 2
return bits
print(to_binary(13)) # "1101"
# Idiomatic one-liner for real code: bin(13)[2:]
P50
Simple Calculator Function
One function, four operators, one guarded edge case.
Simple Calculator Function
One function, four operators, one guarded edge case.
Approach: branch on the operator string and return the matching arithmetic result. Division needs an explicit guard for a zero divisor — dividing by zero is exactly the kind of edge case a calculator function should never silently get wrong.
JavaScript
function calculate(a, b, operator) {
switch (operator) {
case "+": return a + b;
case "-": return a - b;
case "*": return a * b;
case "/":
if (b === 0) throw new Error("Cannot divide by zero"); // guard the risky case
return a / b;
default:
throw new Error(`Unknown operator: ${operator}`);
}
}
console.log(calculate(6, 3, "+")); // 9
console.log(calculate(6, 3, "/")); // 2Python
def calculate(a: float, b: float, operator: str) -> float:
if operator == "+":
return a + b
if operator == "-":
return a - b
if operator == "*":
return a * b
if operator == "/":
if b == 0:
raise ValueError("Cannot divide by zero") # guard the risky case
return a / b
raise ValueError(f"Unknown operator: {operator}")
print(calculate(6, 3, "+")) # 9
print(calculate(6, 3, "/")) # 2.02. Key Takeaways
- Every correct recursive function needs two things: a base case that stops it, and a recursive call whose input is provably closer to that base case than the current call.
- A stack is the right tool whenever "most recently opened, must close first" matters — balanced brackets, undo history, and call stacks themselves all follow that same last-in-first-out rule.
- Binary search's halving only works because the data is sorted first — sorting once and searching many times is almost always worth the up-front cost.