/ THE IDEA
To scan a folder: inspect its files, then scan each child folder. The procedure calls itself on a smaller piece of the structure. A base case—such as a folder with no children—stops the chain. Each unfinished call keeps a small note on the call stack so the program knows where to return after the child finishes.
THE FORMAL IDEA
work(tree) = work(node) + Σ work(each child tree)
| node = the current folder or item | | tree = the whole nested structure; child tree = one smaller nested part below the current item | | Σ means repeat and add across all children |
|
RUN THE TINY EXAMPLE
Search Project/ for report.txt
Scan Project/ → not there; children are Docs/ and Code/ Scan Docs/ → find Notes/ → find report.txt Empty folder → return immediately: that is the base case
|
The same three-line idea works whether the target is one level deep or one hundred, because each call only needs to understand its current folder.
/ SO WHAT?
Recursion is most natural when each part can contain smaller parts with the same shape. Instead of writing separate logic for child, grandchild and great-grandchild, define one trustworthy local rule and let the structure determine repetition.
ONE CAVEAT |
| A missing base case can recurse forever, and very deep structures can overflow the call stack. An explicit stack or queue can perform the same traversal iteratively when depth is risky. |
KEEP THIS
Recursion solves a nested structure by applying one local rule to successively smaller copies of the same problem.
|
NEXT: How order appears from a crowd
|