Introduction

Fibonacci is famous, but it is actually a poor first example of practical recursion because the naive version is inefficient and encourages the wrong lesson. A better example is traversing a tree-like structure, because the recursive shape of the code matches the recursive shape of the data.

Directory traversal, nested comments, syntax trees, and JSON documents all fit this pattern. You solve the whole problem by solving the same problem on each child.

Why Tree Traversal Is a Better Example

Recursion is most useful when a problem can be defined in terms of smaller versions of itself. Trees are ideal because every node can contain more nodes of the same kind.

That gives you a natural structure:

• a base case for leaves or empty nodes
• a recursive step for children

Unlike naive Fibonacci, tree traversal is not recursion for its own sake. It models the problem directly.

A Simple Recursive Example

The code below counts all values stored in a nested tree represented with Python dictionaries.

1tree = {
2    "value": 10,
3    "children": [
4        {
5            "value": 20,
6            "children": []
7        },
8        {
9            "value": 30,
10            "children": [
11                {"value": 40, "children": []}
12            ]
13        }
14    ]
15}
16
17
18def sum_tree(node):
19    total = node["value"]
20
21    for child in node["children"]:
22        total += sum_tree(child)
23
24    return total
25
26
27print(sum_tree(tree))

The function is short because the recursive call expresses the main idea clearly: the sum of a tree is the node's own value plus the sum of every child subtree.

How the Base Case Works

In this example, the base case is implicit. A leaf node has an empty children list, so the loop runs zero times and the function simply returns that node's own value.

You can also write the base case explicitly:

1def sum_tree(node):
2    if not node["children"]:
3        return node["value"]
4
5    total = node["value"]
6    for child in node["children"]:
7        total += sum_tree(child)
8    return total

Both versions are correct. The first is just slightly cleaner.

Why This Example Teaches the Right Lessons

Tree recursion teaches several important ideas at once:

• identifying a base case
• reducing a problem to smaller subproblems
• trusting recursive calls to solve the smaller parts
• understanding call-stack depth

It also maps to many real tasks:

• walking a file system
• rendering nested UI components
• evaluating arithmetic expression trees
• traversing DOM nodes or ASTs

That makes it more useful than a mathematically cute example that you may never use in real software.

Iterative Equivalent

Recursion is not mandatory. The same traversal can be written iteratively with an explicit stack:

1def sum_tree_iterative(root):
2    total = 0
3    stack = [root]
4
5    while stack:
6        node = stack.pop()
7        total += node["value"]
8        stack.extend(node["children"])
9
10    return total

Showing both versions is helpful because it makes the connection between recursive calls and stack-based state management explicit.

Common Pitfalls

• Using Fibonacci as the default recursion example and teaching exponential work by accident.
• Forgetting a base case, which leads to infinite recursion.
• Choosing recursion for data that is not naturally recursive.
• Ignoring worst-case depth when the tree or nested structure may be very deep.
• Memorizing the pattern mechanically instead of understanding the smaller-subproblem idea.

Summary

• Tree traversal is a better recursion example than naive Fibonacci.
• Recursive code works well when the data itself has recursive structure.
• A good recursive solution needs a base case and a smaller-subproblem step.
• File systems, nested JSON, and syntax trees are practical recursion problems.
• Learning the iterative equivalent helps make recursion easier to reason about.