Foundations Solve self-similar problems

Recursion

Solve the smaller problem.

JSON.stringify on a nested object and a recursive walk over a folder both solve the whole by solving each part the same way. A tasting menu is a recipe made of dishes, and a dish can contain more dishes. Price the whole menu by pricing each smaller recipe first, then adding its answer to the caller. That is recursion: one rule for the base case, one for the smaller case, and a return that carries the result back up. Let’s make the same work explicit when the input’s depth is not yours to trust.

TypeScriptGoOne recipe tree, two implementations.

01 / The idea

One dish can contain the same problem.

You’re pricing a tasting menu. An ingredient has a price. A dish has its own packaging cost and a list of children, some of which are dishes in their own right. The whole menu asks the same question as one dish: what does everything below this node cost?

A loop can total the immediate children, but it needs another plan for children that contain children. Recursion lets the function ask the same function to solve one smaller problem. The caller does not need to know how many levels are below it.

02 / Name the rule

Stop at a leaf; otherwise trust the same rule below.

The function needs two cases. Base case: a recipe with no children returns its own cost. Recursive case: start with the dish’s own cost, call the same function for every child, and add each returned cost. Each call moves to a smaller piece of the tree.

The rule must make progress and must stop. If a function calls itself with the same recipe, it never reaches the base case. If it skips a child, the answer is incomplete. If the input is not a tree, decide whether repeated children are uses to count again or dependencies to memoize; this lesson counts each occurrence and rejects cycles so the shape stays honest.

What returns carryThe caller is waiting with a partial total

When Starter calls Soup, Starter keeps its own partial total and the place it resumes. Soup returns 140 cents; Starter adds it and calls Bread. The return value is ordinary data, but the waiting call is what makes the nesting visible.

03 / Follow one operation

Open the recipe, then unwind it.

The animation starts with Espresso, where the base case is visible. It then prices Breakfast box and the nested Tasting menu. Watch the open calls become a path down the tree; when a leaf returns, the caller resumes and adds it.

The fourth chapter runs the iterative version. Nothing about the answer changes: the function’s pending child position and partial total have moved into an explicit frame.

Playback controls

Recursion

Solve the smaller recipe, then add its answer.

Moderecursive

Returned—

Frames at once1

recipe tree

Espresso €1.20

recursive frames · newest on top

No frames open.

caller

Open Espresso, step 1 of 2. No children: this is the base case.

01/ 05

recursive total for Espresso

Follow the smaller recipe.

Open Espresso, step 1 of 2. No children: this is the base case.

Reduced motion: choose a scene to see its completed state.

Read this scene

Open Espresso, step 1 of 2. No children: this is the base case.

recursive total for Espresso.

Try the example by reading

A leaf is the base case: Espresso returns €1.20. Breakfast box adds Coffee, Toast, and Jam to its own 25 cents. The tasting menu opens Starter, Main, and Dessert, then returns their totals upward to €9.00. The iterative version keeps the same frames in an explicit stack. A wide seven-node tree opens two frames; a deep eight-node tree opens eight.

Change the recipe and the frames

Run the same nested data recursively or with an explicit stack. The result is the same; the frames are what change when the shape gets deep.

Recipe shape

Implementation

Choose a recipe and implementation, then measure it.

Total: €9.00
Recipes: 10
Frames at once: 3

Inspect each open and close

Stepping replays the trace; it does not calculate the recipe a second time.

Open Tasting menu, step 1 of 20. 3 children wait below it.

Open Tasting menu at depth 0.
Open Starter at depth 1.
Open Soup at depth 2.
Close Soup and return €1.40.
Open Bread at depth 2.
Close Bread and return €0.90.
Close Starter and return €2.30.
Open Main at depth 1.
Open Pasta at depth 2.
Close Pasta and return €2.50.
Open Sauce at depth 2.
Close Sauce and return €1.10.
Close Main and return €3.60.
Open Dessert at depth 1.
Open Cake at depth 2.
Close Cake and return €1.90.
Open Cream at depth 2.
Close Cream and return €0.70.
Close Dessert and return €2.60.
Close Tasting menu and return €9.00.

Moderecursive

Returned—

Frames at once3

recipe tree

Tasting menu +€0.50
Starter +€0.00
Soup €1.40
Bread €0.90
Main +€0.00
Pasta €2.50
Sauce €1.10
Dessert +€0.00
Cake €1.90
Cream €0.70

recursive frames · newest on top

No frames open.

caller

Open Tasting menu, step 1 of 20. 3 children wait below it.

The display uses five named recipes and keeps every trace visible. The source accepts at most 128 nodes and depth 64; both bounds are teaching limits, not runtime guarantees.

Watch restarts when you return. Step through keeps your selected step. Try it measures a fresh recipe and shows the recorded events without running the calculation again.

04 / Read the shape

Recursive code and written-down frames ask the same question.

Basic form is evaluate: the base case and the recursive case in total, then the same walk with explicit frames. In the wild adds a caller that prices a menu and reports the work. At the call site runs both modes over the same data, so parity is not a claim hidden in the prose.

Read in

Compare with

evaluate states the base case and the recursive case in total, then does the same walk with explicit frames. Validation also uses an explicit stack, so the depth limit holds in both modes.

TypeScriptReading

recipes.ts

// Both versions visit each recipe once and return its own cost plus the costs of its children.
// A leaf is the base case. The trace is optional: it makes the same open/close order visible in
// the lesson without changing the value being calculated.
export function evaluate(root: Recipe, mode: Mode, trace = false): Evaluation {
	const nodes = validateRecipe(root);
	const steps: Step[] = [];
	let peakFrames = 0;

	if (mode === 'recursive') {
		function total(recipe: Recipe, depth: number): number {
			peakFrames = Math.max(peakFrames, depth + 1);
			if (trace) steps.push({ kind: 'open', name: recipe.name, depth });
			let cents = recipe.cents;
			for (const child of recipe.children) cents += total(child, depth + 1);
			if (trace) steps.push({ kind: 'close', name: recipe.name, depth, cents });
			return cents;
		}

		return { mode, totalCents: total(root, 0), nodes, peakFrames, steps };
	}

	type Frame = { recipe: Recipe; next: number; cents: number; depth: number };
	const stack: Frame[] = [{ recipe: root, next: 0, cents: root.cents, depth: 0 }];
	peakFrames = 1;
	if (trace) steps.push({ kind: 'open', name: root.name, depth: 0 });
	while (stack.length) {
		const frame = stack[stack.length - 1];
		if (frame.next < frame.recipe.children.length) {
			const child = frame.recipe.children[frame.next++];
			stack.push({ recipe: child, next: 0, cents: child.cents, depth: frame.depth + 1 });
			peakFrames = Math.max(peakFrames, stack.length);
			if (trace) steps.push({ kind: 'open', name: child.name, depth: frame.depth + 1 });
			continue;
		}
		stack.pop();
		if (trace)
			steps.push({
				kind: 'close',
				name: frame.recipe.name,
				depth: frame.depth,
				cents: frame.cents
			});
		const parent = stack[stack.length - 1];
		if (parent) parent.cents += frame.cents;
		else return { mode, totalCents: frame.cents, nodes, peakFrames, steps };
	}
	throw new Error('unreachable empty recipe stack');
}

GoAlongside

recipes.go

// Both versions visit every recipe once. A leaf returns its own cost; a dish adds its own
// packaging cost to the returned costs of its children. The trace only records the same
// open/close events the page draws.
func Evaluate(root Recipe, mode Mode, trace bool) (Evaluation, error) {
	nodes, err := validateRecipe(root)
	if err != nil {
		return Evaluation{}, err
	}
	result := Evaluation{Mode: mode, Nodes: nodes}
	if mode == Recursive {
		var total func(Recipe, int) int
		total = func(recipe Recipe, depth int) int {
			if depth+1 > result.PeakFrames {
				result.PeakFrames = depth + 1
			}
			if trace {
				result.Steps = append(result.Steps, Step{Kind: "open", Name: recipe.Name, Depth: depth})
			}
			cents := recipe.Cents
			for _, child := range recipe.Children {
				cents += total(child, depth+1)
			}
			if trace {
				result.Steps = append(result.Steps, Step{Kind: "close", Name: recipe.Name, Depth: depth, Cents: cents})
			}
			return cents
		}
		result.TotalCents = total(root, 0)
		return result, nil
	}

	type frame struct {
		recipe Recipe
		next   int
		cents  int
		depth  int
	}
	stack := []frame{{recipe: root, cents: root.Cents}}
	result.PeakFrames = 1
	if trace {
		result.Steps = append(result.Steps, Step{Kind: "open", Name: root.Name})
	}
	for len(stack) > 0 {
		last := len(stack) - 1
		top := &stack[last]
		if top.next < len(top.recipe.Children) {
			child := top.recipe.Children[top.next]
			top.next++
			stack = append(stack, frame{recipe: child, cents: child.Cents, depth: top.depth + 1})
			if len(stack) > result.PeakFrames {
				result.PeakFrames = len(stack)
			}
			if trace {
				result.Steps = append(result.Steps, Step{Kind: "open", Name: child.Name, Depth: top.depth + 1})
			}
			continue
		}
		finished := *top
		stack = stack[:last]
		if trace {
			result.Steps = append(result.Steps, Step{Kind: "close", Name: finished.recipe.Name, Depth: finished.depth, Cents: finished.cents})
		}
		if len(stack) == 0 {
			result.TotalCents = finished.cents
			return result, nil
		}
		stack[len(stack)-1].cents += finished.cents
	}
	return Evaluation{}, errors.New("empty recipe stack")
}

Reading the TypeScriptA return value plus a smaller call

total starts with recipe.cents, then adds each child’s returned value. The local cents belongs to this call; another call gets its own local while this one waits.

Reading the GoA slice holds the explicit frames

Go’s recursive closure follows the same rule. The iterative version stores a frame with the current child index and partial cents, then adds a finished child to the frame below it.

05 / Try a decision

What makes the recursive version need more space?

The wide and deep examples do almost the same amount of work and return the same total. Before you inspect the counts, predict which one keeps more frames open.

06 / Follow the cost

Linear work, height-sized extra space.

For n recipes in a tree, both versions visit each node once: O(n) time. The recursive call stack, or the explicit frame stack, holds one frame for each node on the current path: O(h) extra space, where h is the tree’s height.

Nested recipe costing: work and storage
Operation	Time	Extra space	What it assumes
Price n recipes recursively	`O(n)`	`O(h)`	Every recipe is visited once; h is the greatest nesting depth and determines open call frames.
Price n recipes with explicit frames	`O(n)`	`O(h)`	The written-down frames hold the same pending child position and partial total as recursive calls.
Store the recipe tree	`—`	`O(n)`	The input tree is retained by the caller; this is separate from the traversal’s extra frames.

The input tree itself is not extra traversal space. A wide tree can retain many children in the input while opening only two frames: the root and one child. A chain with the same sort of nodes keeps the whole path open. That is why the input’s node count and the algorithm’s working space are different questions.

The explicit stack does not make the algorithm asymptotically smaller; it makes the storage policy visible. You can cap depth, reject an imported shape, or move the walk out of the runtime call stack. The cost model explains why those are two separate axes.

07 / Give it a real job

Use it when the data already has the same shape.

A recipe editor, an expression evaluator, and a syntax tree all contain smaller values with the same rules as their parent. Recursion keeps the operation next to that shape. If a generated import can be 100,000 levels deep, the explicit-frame version gives the owner a place to enforce a depth limit and report a useful rejection.

The example validates a bounded tree and refuses cycles. A real service also needs to choose a policy for malformed cycles, repeated references, cancellation, and output size. None of those policies appears by magic because the function calls itself.

08 / Make the call

Choose the clearest owner of the pending work.

Use recursion when the structure is a bounded tree and the code’s shape is the explanation. Use an explicit stack when input depth is external, stack limits matter, or you need pause, cancel, checkpoint, or inspect the pending work. Use memoization only when subproblems overlap and the identity and invalidation policy are explicit; shared dependencies turn this tree example into a different problem.

For a flat list, a loop is usually clearer. For a graph, add a visited policy before you recurse; breadth-first and depth-first search shows why a seen set matters. For a parser or component tree, the recursion may be the right model, but the owner still owns the limit.

09 / Take the idea with you

Look for the smaller problem inside the larger one.

Recursion is a way to express a proof and an implementation together: solve the base case, trust the smaller answer, and combine it. The call-stack lesson shows what each open call keeps at runtime. This lesson adds the DSA choice between that natural shape and an explicit stack, plus the cost of the height.

Connections to follow nextRelated lessons

Binary search tree— follow one branch, then repair a tree’s order.
Breadth-first and depth-first search— make traversal order and seen identity explicit.
The call stack and execution— inspect frames, returns, and runtime depth.