Mansori

Recursion Grows a Tree

About this lesson, for parents and teachers

One tiny function, seven lines long, draws a whole tree. The trick is that the function calls itself. Grow one and watch every call happen, then find out what happens when nothing tells it to stop.

Ages 12–14 · about 8 minutes · builds on Functions Are Input-Output Machines

Try this

  1. Press Grow. The lit code line and the call stack show exactly which call is running.
  2. Change the depth slider until the tree makes exactly 127 calls. The formula at the top helps.
  3. Play with turn T and shrink k to make bushy or spiky trees.
  4. Switch Base case off and press Grow. What happens to the stack?

How it works

Recursion is when a function solves a problem by calling itself on a smaller version of the same problem. Our branch function draws one line, then calls branch twice from the tip of that line: once turned left, once turned right, each time a bit shorter and with d one smaller. A tree is just a trunk with two smaller trees on top.

Every recursive function needs a base case: a simple situation it can answer without calling itself. Here it is if (d === 0) return;. Because d goes down by one on every call, it is guaranteed to reach 0. Those calls draw the purple leaves and stop. Without a base case the calls never end.

The computer keeps track of unfinished calls on the call stack. Each call pushes a frame holding its own x, y, angle and d. When a call finishes, its frame pops off and the computer returns to the call below it. That is why the tree grows depth-first: it finishes the whole left side of a branch before starting the right side.

How many calls? Depth 1 makes 1 + 2 = 3 calls (the two children hit the base case). Every extra level doubles the leaves, so depth d makes 2^(d+1) - 1 calls. Depth 6 makes 127, depth 11 makes 4,095. With no base case, the stack fills up until JavaScript throws RangeError: Maximum call stack size exceeded, a real error programmers see.

Where engineers use this

Recursion powers file explorers walking folders inside folders, the JSON parser in your browser, chess engines searching moves, and the fractal plants and terrain in video games and movies.

Words to know

Recursion
A function that calls itself on a smaller version of the problem.
Base case
The condition where a recursive function stops calling itself and simply returns.
Call stack
The computer's list of function calls that have started but not yet finished.
Stack overflow
An error when too many calls pile up on the call stack, usually because the base case is missing or never reached.

Talk about it

Goal: Use a function that calls itself to grow a fractal tree, and see the base case stop it.

  • Can you describe a tree, a family tree or a set of nesting dolls using the thing itself?
  • Why does d have to get smaller on every call?
  • If each branch split into three instead of two, how fast would the number of calls grow?

Without a screen: Russian dolls or nested boxes: to count the dolls, open one and ask 'how many dolls inside this one?', stopping when a doll does not open (the base case). Or draw a tree on paper by the rule: draw a line, then draw two shorter lines from its tip, and stop when lines are shorter than a fingernail.

Curriculum links: CSTA K-12 2-AP-14 (procedures with parameters), 3A-AP-17 (decompose problems), AP Computer Science A recursion topic; Common Core 8.F (functions)

Questions

What is recursion in simple words?
Recursion is when a function calls itself to solve a smaller piece of the same problem, until it reaches a piece so small it can answer directly. That smallest case is called the base case.

What happens if a recursive function has no base case?
It keeps calling itself forever, each call adding a frame to the call stack, until the stack runs out of space. In JavaScript that throws a RangeError called Maximum call stack size exceeded.

Why is a fractal tree a good example of recursion?
Because a tree really is self-similar: each branch looks like a smaller tree. The code mirrors that exactly, drawing a branch and then drawing two smaller trees from its tip.