Loops and recursion
Two ways to repeat work: loops that walk through data, and functions that call themselves. for, while, break, off-by-one errors, base cases, stack limits, and memoization, with real output.
Part 5 covered making a decision. This part covers the third control structure from part 0: iteration, doing something more than once. There are two ways to do that. A loop repeats a block of code. Recursion has a function call itself on a smaller piece of the problem. Both can solve the same problems; knowing when each one fits is the useful part.
Looping over a collection
Most loops walk through a collection: every item in a list, every line in a file, every row from a query. Python is built around this. Its tutorial puts it this way: “Python’s for statement iterates over the items of any sequence (a list or a string), in the order that they appear in the sequence”, which “differs a bit from what you may be used to in C or Pascal.”
prices = [12, 5, 30]
for price in prices:
print(price)
12
5
30
When you also need the position, ask for it instead of counting yourself:
for i, price in enumerate(prices):
print(i, price)
0 12
1 5
2 30
And when you need a sequence of numbers, range gives you one. Note where it stops:
>>> list(range(5)), list(range(1, 5))
([0, 1, 2, 3, 4], [1, 2, 3, 4])
range(5) is 0 to 4, not 0 to 5. The end is never included, which is exactly what you want for indexes of a list with 5 items.
JavaScript’s equivalent is for...of, which “executes a loop that operates on a sequence of values sourced from an iterable object.” Don’t confuse it with for...in, which “iterates over all enumerable string properties of an object”, so on an array you get the indexes as strings:
const prices = [12, 5, 30];
for (const p of prices) console.log(p); // 12, 5, 30
for (const k in prices) console.log(typeof k, k); // string 0, string 1, string 2
MDN’s advice for arrays: “It is better to use a for loop with a numeric index, Array.prototype.forEach(), or the for...of loop”.
Go: one loop for everything
Go has a single loop keyword. Effective Go says its for “unifies for and while and there is no do-while.” The same keyword covers all three shapes:
// classic counter
for i := 0; i < 3; i++ {
fmt.Print(i, " ")
}
// "while": only a condition
for n != 1 {
// ...
}
// over a collection
for i, p := range prices {
fmt.Println(i, p)
}
PHP: foreach and the reference trap
PHP’s foreach works like Python’s for, with the key available when you want it:
$prices = [12, 5, 30];
foreach ($prices as $i => $price) {
echo "$i $price\n";
}
// 0 12
// 1 5
// 2 30
To change items in place, PHP lets you loop by reference with &. That comes with a well-known trap, documented in the manual: “A reference to the $value of the last array element remains even after the foreach loop. It is recommended to destroy it using unset().” Here’s what happens if you don’t:
$prices = [12, 5, 30];
foreach ($prices as &$p) {
$p = $p * 2;
}
foreach ($prices as $p) { } // reuses $p, which still points at the last item
echo json_encode($prices); // [24,10,10] ← 60 was overwritten
Add unset($p); after the first loop and the result is the expected [24,10,60].
while: repeat until something changes
A while loop repeats as long as a condition is true. It fits when you don’t know in advance how many steps it will take. This one keeps applying a simple rule until the number reaches 1:
n = 10
steps = 0
while n != 1:
n = n // 2 if n % 2 == 0 else 3 * n + 1
steps += 1
print("steps:", steps) # steps: 6
The risk with while is the loop that never ends. Before writing one, ask: what changes on each pass, and how do I know it will eventually make the condition false?
Stopping early: break, continue, and Python’s loop else
breakleaves the loop immediately.continueskips the rest of this pass and moves to the next one.
Python adds an unusual extra: an else on a loop. The tutorial explains: “If the loop finishes without executing the break, the else clause executes.” It’s handy for searches:
for name in ["ana", "budi", "citra"]:
if name.startswith("b"):
print("found", name)
break
else:
print("not found")
With budi in the list this prints found budi; without him it prints not found.
One JavaScript detail worth knowing: “There is no way to stop or break a forEach() loop other than by throwing an exception.” If you might need to stop early, use for...of with break, or methods like find and some that stop on their own.
Off-by-one errors
An off-by-one error “is a logic error that involves a number that differs from its intended value by 1.” Loops are their natural habitat: < vs <=, starting at 0 or 1, including the end or not.
items = ["a", "b", "c"]
for i in range(len(items) + 1):
print(items[i])
a
b
c
IndexError: list index out of range
The easiest way to avoid most of these is to not handle indexes at all: loop over the items directly, and use enumerate or range(len(...)) only when you really need the position.
Recursion: a function that calls itself
Recursion is “a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem.” Every recursive function needs two parts:
- A base case, which “specifies input values for which the function can provide a result directly, without any further recursion.”
- A recursive case, which handles a smaller piece and calls the function on the rest.
def total(items):
if not items: # base case: an empty list sums to 0
return 0
return items[0] + total(items[1:]) # first item + total of the rest
print(total([12, 5, 30])) # 47
For a flat list, a loop is simpler. Recursion shines when the data itself is nested, like folders inside folders, comments with replies, or JSON inside JSON:
def count_files(node):
if isinstance(node, str): # a file
return 1
return sum(count_files(child) for child in node) # a folder
tree = ["a.txt", ["b.txt", "c.txt", ["d.txt"]], "e.txt"]
print(count_files(tree)) # 5
Writing that with loops means keeping your own list of folders still to visit. The recursive version just follows the shape of the data.
When recursion goes wrong: the stack runs out
Each function call takes a little space on the call stack (the stack from part 3). A recursion without a working base case keeps calling until there is no room left. “Base cases are essential because they prevent infinite regress.”
def forever(n):
return forever(n + 1)
RecursionError: maximum recursion depth exceeded
Python raises RecursionError “when the interpreter detects that the maximum recursion depth (see sys.getrecursionlimit()) is exceeded.” The default limit here is 1000. JavaScript has the same kind of safety net:
RangeError: Maximum call stack size exceeded
PHP has no friendly recursion error of its own. The manual warns that “Recursive function/method calls with over 100-200 recursion levels can smash the stack and cause a termination of the current script.” In practice, with a typical memory_limit of 128M, an endless recursion ends like this:
PHP Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 2097152 bytes)
This is also why very deep data, like a list with a hundred thousand items, is better handled with a loop than with recursion.
The hidden cost: repeating work
Some recursive solutions look elegant and are painfully slow, because they solve the same small problem over and over. The classic example is Fibonacci numbers:
def fib(n):
return n if n < 2 else fib(n - 1) + fib(n - 2)
To compute fib(25) this way, the function is called 242,785 times. The fix is to remember answers you’ve already computed, called memoization. Python has it built in:
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
return n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)
Same result (75025), 26 calls. That gap between 242,785 and 26 is a preview of part 10 on algorithms: how you solve a problem can matter far more than how fast your computer is.
Loop or recursion?
- Use a loop for flat data, counting, and anything that might be very long. It’s usually clearer and never hits a stack limit.
- Use recursion when the data or the problem is nested: trees, folders, menus, parsers. The code then mirrors the structure.
- Either way, be sure it stops: a condition that eventually becomes false, or a base case that is always reached.
Try it yourself
- Rewrite
totalwith aforloop. Which version is easier to read? - Change the
whileexample to start at 27 and count the steps. Guess first; it’s far more than you’d expect. - Call the plain
fib(30)andfib_memo(30)and count the calls for each. - In JavaScript, try to
breakout of aforEach, then rewrite it withfor...of.
Summary
- Loops repeat a block; recursion solves a problem by solving smaller versions of it.
- Prefer looping over items directly (
for item in items,for...of,foreach,rangein Go) instead of managing indexes. In PHP,unset()the variable after a by-referenceforeach. range(n)stops beforen. Many off-by-one bugs live at the edges of loops.- Every
whileloop and every recursive function needs a guaranteed way to stop. - Recursion fits nested data; deep recursion hits the stack limit (
RecursionError,RangeError). - Recomputing the same thing is expensive; memoization can turn hundreds of thousands of calls into a few dozen.
References
- More Control Flow Tools: for Statements, break and continue, else clauses on loops, Python tutorial.
- Built-in Exceptions: RecursionError, Python documentation.
- Effective Go: For, The Go Programming Language.
- for…of, for…in, and Array.prototype.forEach(), MDN.
- Recursion (computer science) and Off-by-one error, Wikipedia.
- foreach and User-defined functions, PHP Manual.