Recursion and L-Systems

A recursive function is one that calls itself on a smaller version of the same problem. It sounds circular, and it would be - an infinite loop - if it were not for the one rule that makes recursion safe: every recursive function must have a base case, a condition where it stops calling itself and simply returns an answer. Without a base case you get a RecursionError; with one, the calls unwind cleanly.

Here is recursion doing something a designer cares about - subdividing a length into equal pieces by halving, depth times:

def subdivide(length, depth):
    if depth == 0:              # base case: stop here
        return [length]
    half = length / 2
    return subdivide(half, depth - 1) + subdivide(half, depth - 1)

print(subdivide(4.0, 2))        # [1.0, 1.0, 1.0, 1.0]

Read it as a decision: if we have subdivided enough (depth == 0), stop and return this piece; otherwise, split in half and ask the same function to subdivide each half one level less. Each call reduces depth by one, so it marches toward the base case and terminates. The mental model is a stack of nested tasks: the function keeps opening smaller copies of itself, then closes them from the innermost out. Anything with a naturally nested or self-similar structure - subdivided grids, tree menus, folder trees, branching geometry - is often clearest expressed this way.

If that feels slippery at first, you are in good company - recursion is the concept that most reliably makes newcomers pause, because the function seems to use itself before it is finished. The trick is to trust the recursion: assume the inner call already does its job correctly for a smaller input, and you only have to get two things right. First, the base case - what to return when the problem is as small as it gets. Second, the recursive step - how to build the answer for a bigger problem out of the answer for a smaller one. Get those two pieces right and the whole tower of calls takes care of itself; you never have to trace every level in your head, which is a relief, because for anything interesting there are far too many levels to hold at once.

You can often write the same thing with a loop or with recursion, and for flat, linear work a loop is usually simpler and faster. Recursion earns its place when the structure is nested - when each piece contains smaller pieces of the same kind. A classic is a fractal rule like the Koch curve, where each line segment is replaced by four smaller segments, and each of those by four more:

def koch(length, depth):
    if depth == 0:
        return [("F", length)]     # F = draw forward
    third = length / 3
    seg = koch(third, depth - 1)
    return seg + [("L", 60)] + seg + [("R", 120)] + seg + [("L", 60)] + seg

print(len(koch(1.0, 2)))            # grows fast: 4 segments per level

Each level multiplies detail by four - two levels give 16 draw steps, five levels give over a thousand, all from one rule. That explosive growth is the point and the danger: recursion generates enormous complexity from tiny descriptions, but go too deep and you overwhelm memory or the recursion limit. Start shallow (depth 2 or 3), see the result, then increase depth deliberately. The honest guideline: use a loop for repetition, use recursion for self-similarity - and always keep the base case in sight.

An L-system (Lindenmayer system, named after the biologist who devised it to model plant growth) is a beautifully simple idea. You start with a short string called the axiom, and you have rules that say how to rewrite each symbol. On every generation, you replace every symbol at once according to the rules, and the string gets longer and more structured. It is recursion expressed as text rewriting.

def grow(axiom, rules, generations):
    s = axiom
    for _ in range(generations):
        s = "".join(rules.get(ch, ch) for ch in s)
    return s

rules = {"F": "F[+F]F[-F]F"}
print(grow("F", rules, 2))

That grow function is the whole engine: for each generation, every character is looked up in rules (and left unchanged if it has no rule, via rules.get(ch, ch)). The symbols are a little turtle-graphics language: F means draw forward, + and - mean turn right and left by a fixed angle, and [ and ] mean 'remember where I am' and 'jump back there' - which is exactly how you make a branch that returns to the trunk. One rule, applied twice, already produces a bushy instruction string; applied five times it describes a whole plant.

What makes this so powerful is that the rule and the drawing are cleanly separated. The grow function knows nothing about geometry - it just rewrites text - and the turtle knows nothing about biology - it just follows symbols. That separation means you can change the look (the turn angle, the step length, the drawing tool) without touching the grammar, and change the grammar without touching the drawing. It is the same discipline good scripts always reward: small pieces that each do one thing, snapped together. Historically this is why L-systems succeeded as models of real botany - Lindenmayer could capture the growth rule of an actual plant species in a compact grammar, then let the interpreter render it - and it is why they remain such a satisfying introduction to generative form: the entire creative space lives in a handful of characters you can edit and immediately re-grow.

An L-system string is only instructions; to see form you feed it to a turtle - an imaginary pen with a position and a heading that reads the string one symbol at a time. F moves the pen forward drawing a line, +/- rotate the heading, and [/] push and pop the state onto a stack so branches spring off and snap back. Here is the interpreter producing line segments as coordinate pairs:

import math

def draw(s, step=1.0, angle=25):
    x, y, a = 0.0, 0.0, 90.0     # start pointing up
    stack, lines = [], []
    for ch in s:
        if ch == "F":
            nx = x + step * math.cos(math.radians(a))
            ny = y + step * math.sin(math.radians(a))
            lines.append(((x, y), (nx, ny)))
            x, y = nx, ny
        elif ch == "+": a -= angle
        elif ch == "-": a += angle
        elif ch == "[": stack.append((x, y, a))
        elif ch == "]": x, y, a = stack.pop()
    return lines

print(len(draw(grow("F", {"F": "F[+F]F[-F]F"}, 3))))

Those ((x, y), (nx, ny)) pairs are geometry you can hand to any drawing tool - matplotlib for a sketch, or Rhino/Grasshopper to build real curves (Module 6). The three knobs - the rule, the turn angle, and the number of generations - each change the plant's character completely: a small angle gives a tall narrow tree, a wide angle a spreading bush. That is the joy of L-systems for a designer: a handful of parameters, an entire family of organic forms.

You can push the grammar further. Add a stochastic twist by choosing between two rules at random for each F (a stochastic L-system), and every plant grows a little differently while keeping the same species - which is exactly where this lesson meets the randomness of the previous one, seed and all. Or make the turn angle itself a parameter that drifts with a noise function, and the tree leans and sways. The point is that L-systems are not a fixed trick; they are a small, extensible language for growth that you can bend toward whatever organic system you are modelling.

It would be a mistake to file recursion away as 'the L-system thing'. Self-similar structure is everywhere in design and design software, and once you recognise it you will reach for recursion naturally. Subdividing a plan or facade is recursive - split a rectangle, then split each half the same way, stopping when the pieces are small enough - and this is the idea behind quadtree and binary space partitioning layouts used for automatic room division and responsive grids. Space-filling curves, fractal ornament, and tree diagrams of every kind - a spanning structure, an org chart, a decision tree - are all recursive in shape.

Recursion is also the honest way to walk anything nested. A folder that contains folders that contain folders is a tree, and a recursive function that processes a folder and then calls itself on each sub-folder is the clean way to, say, gather every drawing in a deep project directory (a task Module 8 returns to). The same applies to nested data - a JSON structure with lists inside dictionaries inside lists - where a recursive walker handles arbitrary depth that a fixed set of loops cannot.

The judgement call is always the same. Reach for recursion when the structure genuinely nests and each part contains smaller parts of its own kind; stick with a plain loop when the work is flat and linear. And whichever you choose, keep the two safety habits in view: write the base case first, and make sure every recursive call moves measurably toward it. Recursion rewards you with descriptions that match the structure of the problem - which is why, for branching, subdivision and nesting, it so often reads more clearly than the loop-and-stack alternative.