Recursion and Closures Through Small Traversal Problems

Ruby source files are converted directly from the English source tree.
en/topic_13_recursion_closures

Overview

Why this topic matters 💡

Recursion and closures are both powerful ideas, but students often meet them as isolated syntax tricks. This topic teaches them through a sequence of small problems: recurse over nested structures first, then build closures that capture query behavior, then combine both ideas in one traversal service.

Learning outcomes 🎯

By the end of this topic, students should be able to:

explain the difference between a recursive step and a base case;
use recursion to walk nested arrays or tree-like hashes;
explain what a closure captures from its surrounding scope;
build a small function factory that returns a lambda with remembered state;
combine recursive traversal with an injected closure to keep logic flexible.

Assessment focus ✅

Students should be able to explain why the recursive traversal and the matching rule are separated instead of embedded into one large method.

Short Note

Recursion is useful when the data shape repeats itself:

a nested array contains arrays;
a tree node contains child nodes;
each step looks like a smaller version of the whole problem.

Closures are useful when behavior should remember a value from the place where it was created:

a predicate that remembers a search term;
a counter that remembers its running total;
a formatter that remembers a prefix or rule.

Ruby beauty in this topic:

recursion can stay compact when the base case is explicit;
lambdas and blocks make small captured behaviors easy to express;
combining them can produce elegant traversal code.

Ruby caution in this topic:

recursion becomes confusing if the base case is not obvious;
closures can hide important state if they are created too casually;
not every nested problem needs recursion if iteration would be clearer.

Reflection prompt:

What part of the advanced solution belongs to the traversal, and what part belongs to the captured closure?

Worked Examples

Example 1: Nested number structures 💡

Summing nested numbers is a useful first recursion exercise because the repeated shape is obvious. Each child is either:

already a value, or
another structure of the same kind.

That makes it easier for students to see what recursion is doing.

Example 2: Search predicates as closures 💡

A closure is realistic when a user provides a search term and the code needs a small reusable matcher:

matcher = TitleMatchers.containing("ruby")
matcher.call("Ruby Blocks")
# => true

worked_examples.md
ruby

This is better than hard-coding the search term inside the traversal.

Example 3: Recursive query over a content tree 💡

Documentation menus, comment threads, and category trees all use the same pattern:

each node has a title;
each node may have children;
a traversal should decide what to collect.

That makes recursion plus closure a strong teaching combination.

Cheatsheet

Recursive shape

def sum(node)
  return node if node.is_a?(Integer)

  node.sum { |child| sum(child) }
end

cheatsheet.md
ruby

Recursive tree traversal

def collect(node, paths = [], prefix = [])
  current = prefix + [node[:title]]
  paths << current.join(" > ") if node[:children].empty?
  node[:children].each { |child| collect(child, paths, current) }
  paths
end

cheatsheet.md
ruby

Closure factory

def self.containing(term)
  ->(title) { title.downcase.include?(term.downcase) }
end

cheatsheet.md
ruby

Sprint mindset 🏃

Sprint 1: recursive base case and recursive case
Sprint 2: recursive traversal over a tree
Sprint 3: closure factory for reusable predicates
Sprint 4: combine the closure with recursive traversal

Study Guide

Topic purpose 🎯

Learn recursion and closures through short sprints. Students should first master recursive structure on a small example, then build a closure that captures search behavior, then combine the two ideas in one object.

Study sequence 🪜

Read overview.md.
Read shortnote.md.
Study worked_examples.md.
Keep cheatsheet.md open while reading example.rb.
Complete the basic exercise.
Complete the advanced exercise.

Sprint plan 🏃

Sprint 1: Basic recursion

identify the base case;
identify the recursive case;
trust the smaller call to solve the smaller problem.

Sprint 2: Recursive tree traversal

walk a nested tree;
accumulate a result outside the recursive call;
keep the current path explicit.

Sprint 3: Closure factory

create a matcher that remembers a value from its creation site;
call the matcher later inside another object.

Sprint 4: Combine recursion and closure

keep the traversal generic;
inject the matching rule as a closure;
return collected results instead of printing directly.

Optional extension ideas

recursive comment counting;
recursive file tree size;
a closure-based formatter that captures indentation;
tree traversal with both filtering and mapping.

Reflection questions 🤔

Why is a base case required before recursion is safe?
What value is remembered by the closure in the advanced exercise?
Why is it cleaner to inject a matcher than to hard-code the query rule inside the traversal?

Source Files and Tests

Ruby source files are converted directly from the English source tree.

# EXAMPLE CODE
# Topic: topic_13_recursion_closures
#
# Purpose:
# - This file demonstrates recursion over a nested array/integer structure.
# - It should pass tests from the beginning.
# - Read it before solving the tree traversal and closure exercises.

class NestedNumberSummer
  def sum(node)
    return node if node.is_a?(Integer)

    node.sum { |child| sum(child) }
  end
end

en/topic_13_recursion_closures/example.rb
Ruby course source

# STUDENT TASK (BASIC)
# Topic: topic_13_recursion_closures
#
# What to do:
# - Traverse a nested category tree recursively.
# - Return the full leaf paths instead of printing directly.
# - Keep the current path explicit so the recursion is easy to follow.
#
# Expected outcome:
# - You can solve a small tree problem with a clear base case and recursive case.

class CategoryPaths
  def paths(tree, prefix = [])
    current_path = prefix + [tree[:title]]
    return [current_path.join(" > ")] if tree[:children].empty?

    tree[:children].flat_map { |child| paths(child, current_path) }
  end
end

en/topic_13_recursion_closures/basic_exercise.rb
Ruby course source

# STUDENT TASK (ADVANCED)
# Topic: topic_13_recursion_closures
#
# Academic purpose:
# - Combine recursive traversal with a closure that captures query behavior.
# - Show that recursion can stay generic while the matching rule remains flexible.
#
# Real-world use case:
# - Content trees, nested menus, and documentation sidebars often need searches such as
#   "find all titles containing this term."
# - A matcher closure lets the search term live outside the traversal logic.
#
# Why Ruby is beautiful here:
# - Lambdas make small captured behaviors easy to create.
# - The traversal stays focused on the tree shape.
# - The matching rule can change without rewriting the recursion.
#
# What to do:
# - Build one closure factory that remembers a search term.
# - Build one recursive query object that uses the closure to decide what to collect.
# - Return matching node titles as ordinary arrays.
#
# Expected outcome:
# - Advanced tests pass and you can explain what the closure captures.

module TitleMatchers
  def self.containing(term)
    ->(title) { title.downcase.include?(term.downcase) }
  end
end

class TreeQuery
  def initialize(matcher:)
    @matcher = matcher
  end

  def matching_titles(tree)
    results = []
    visit(tree, results)
    results
  end

  private

  def visit(node, results)
    results << node[:title] if @matcher.call(node[:title])
    node[:children].each { |child| visit(child, results) }
  end
end

en/topic_13_recursion_closures/adv_exercise.rb
Ruby course source

# ANSWER KEY (BASIC)
# Topic: topic_13_recursion_closures
#
# Solution idea:
# - Build the current path before descending.
# - If the node has no children, the recursion stops and returns one completed path.
# - Otherwise, recurse into each child and flatten the collected paths.

class CategoryPaths
  def paths(tree, prefix = [])
    current_path = prefix + [tree[:title]]
    return [current_path.join(" > ")] if tree[:children].empty?

    tree[:children].flat_map { |child| paths(child, current_path) }
  end
end

en/topic_13_recursion_closures/answer_basic_exercise.rb
Ruby course source

# ANSWER KEY (ADVANCED)
# Topic: topic_13_recursion_closures
#
# Solution idea:
# - The closure remembers the `term` value from where it was created.
# - `TreeQuery` only knows how to walk the tree.
# - The matcher decides which titles are worth collecting.

module TitleMatchers
  def self.containing(term)
    ->(title) { title.downcase.include?(term.downcase) }
  end
end

class TreeQuery
  def initialize(matcher:)
    @matcher = matcher
  end

  def matching_titles(tree)
    results = []
    visit(tree, results)
    results
  end

  private

  def visit(node, results)
    results << node[:title] if @matcher.call(node[:title])
    node[:children].each { |child| visit(child, results) }
  end
end

en/topic_13_recursion_closures/answer_adv_exercise.rb
Ruby course source

# This spec is your learning companion for topic_13_recursion_closures.
#
# How to use this file:
# 1) Run tests and observe failures or successes.
# 2) Keep the EXAMPLE specs green from the beginning.
# 3) Implement the BASIC exercise as sprint 2: recursive path collection.
# 4) Implement the ADVANCED exercise as sprint 3 and 4: closure factory plus recursive query.
#
# Expected final result:
# - All examples in this file pass.
# - You understand both recursion and closure capture in a practical setting.

require_relative "../example"
require_relative "../basic_exercise"
require_relative "../adv_exercise"

RSpec.describe "topic_13_recursion_closures" do
  describe "EXAMPLE purpose: understand recursion through a repeated data shape" do
    it "sums nested integers recursively" do
      summer = NestedNumberSummer.new

      expect(summer.sum([1, [2, 3], [4, [5]]])).to eq(15)
      expect(summer.sum([7, [1, [2]]])).to eq(10)
    end
  end

  describe "BASIC EXERCISE purpose: traverse a tree recursively as a small sprint" do
    it "returns leaf paths from a nested category tree" do
      tree = {
        title: "Docs",
        children: [
          {
            title: "Ruby",
            children: [
              { title: "Blocks", children: [] },
              { title: "Enumerable", children: [] }
            ]
          },
          {
            title: "SQL",
            children: [
              { title: "SQLite", children: [] }
            ]
          }
        ]
      }

      paths = CategoryPaths.new.paths(tree)

      expect(paths).to eq(
        [
          "Docs > Ruby > Blocks",
          "Docs > Ruby > Enumerable",
          "Docs > SQL > SQLite"
        ]
      )
    end
  end

  describe "ADVANCED EXERCISE purpose: combine closure capture with recursive traversal" do
    it "uses a matcher closure to collect matching titles" do
      tree = {
        title: "Docs",
        children: [
          {
            title: "Ruby Basics",
            children: [
              { title: "Ruby Blocks", children: [] },
              { title: "Enumerable", children: [] }
            ]
          },
          {
            title: "SQL",
            children: [
              { title: "SQLite with Ruby", children: [] }
            ]
          }
        ]
      }

      matcher = TitleMatchers.containing("ruby")
      query = TreeQuery.new(matcher: matcher)

      expect(query.matching_titles(tree)).to eq(
        ["Ruby Basics", "Ruby Blocks", "SQLite with Ruby"]
      )
    end
  end
end

en/topic_13_recursion_closures/tests/topic_13_recursion_closures_spec.rb
Ruby course source

#!/usr/bin/env bash
set -euo pipefail

SCRIPT_DIR="$(cd "$(dirname "${BASH_SOURCE[0]}")" && pwd)"
ROOT_DIR="$(cd "${SCRIPT_DIR}/.." && pwd)"

exec "${ROOT_DIR}/run_tests.sh" "$(basename "${SCRIPT_DIR}")"

en/topic_13_recursion_closures/run_topic_tests.sh
Ruby course source

Study Prompts

Read the spec first and identify which behaviors belong to the example, basic exercise, and advanced exercise.
Attempt the exercises before opening the answer files, then compare the design choices.

Next → Generated from book.sqlite through the Online Ebook Framework static publisher.