package main
import (
"flag"
"fmt"
"strings"
"time"
"algo/metrics"
)
// Folder is a nested collection — a library organised into sub-collections,
// which is the smallest structure that is genuinely recursive.
type Folder struct {
Name string
Items []Item
Subs []*Folder
}
// ── The same walk, twice ────────────────────────────────────────────────
// WalkRecursive visits every item. The call stack remembers which folder to
// return to; you never write that down yourself.
func WalkRecursive(f *Folder, c *metrics.Counter) int {
n := len(f.Items)
c.Hit()
for _, sub := range f.Subs {
n += WalkRecursive(sub, c)
}
return n
}
// WalkIterative visits every item in exactly the same order — but the stack of
// folders still to visit is one YOU keep, using lesson 4's structure.
//
// This is the whole point of the lesson: the two functions are the same
// algorithm. Recursion did not remove the stack. It hid it.
func WalkIterative(root *Folder, c *metrics.Counter) int {
stack := []*Folder{root}
n := 0
maxDepth := 0
for len(stack) > 0 {
if len(stack) > maxDepth {
maxDepth = len(stack)
}
f := stack[len(stack)-1]
stack = stack[:len(stack)-1]
n += len(f.Items)
c.Hit()
// Push children in reverse so they come off in the original order.
for i := len(f.Subs) - 1; i >= 0; i-- {
stack = append(stack, f.Subs[i])
}
}
return n
}
// buildTree makes a folder tree `depth` deep with `branch` sub-folders each.
func buildTree(depth, branch, perFolder int, id *int) *Folder {
f := &Folder{Name: fmt.Sprintf("folder-%d", *id)}
for i := 0; i < perFolder; i++ {
*id++
f.Items = append(f.Items, Item{ID: *id, Title: fmt.Sprintf("track-%d", *id)})
}
if depth > 0 {
for i := 0; i < branch; i++ {
*id++
f.Subs = append(f.Subs, buildTree(depth-1, branch, perFolder, id))
}
}
return f
}
// chain builds a tree that is one long line — depth n, no branching. This is
// what makes recursion depth equal to n.
func chain(n int) *Folder {
root := &Folder{Name: "root"}
cur := root
for i := 0; i < n; i++ {
next := &Folder{Name: fmt.Sprintf("f%d", i), Items: []Item{{ID: i}}}
cur.Subs = []*Folder{next}
cur = next
}
return root
}
func cmdWalk(args []string) error {
fs := flag.NewFlagSet("walk", flag.ContinueOnError)
depth := fs.Int("depth", 3, "folder nesting depth")
branch := fs.Int("branch", 3, "sub-folders per folder")
per := fs.Int("per", 2, "items per folder")
if err := fs.Parse(args); err != nil {
return err
}
id := 0
root := buildTree(*depth, *branch, *per, &id)
var cr, ci metrics.Counter
nr := WalkRecursive(root, &cr)
ni := WalkIterative(root, &ci)
fmt.Printf("tree: depth=%d branch=%d items-per-folder=%d\n\n", *depth, *branch, *per)
fmt.Printf("%-24s %10s %14s\n", "walk", "items", "folders visited")
fmt.Printf("%-24s %10d %14d\n", "recursive", nr, cr.N())
fmt.Printf("%-24s %10d %14d\n", "iterative (your stack)", ni, ci.N())
if nr == ni && cr.N() == ci.N() {
fmt.Println("\nidentical — same algorithm, different place to keep the stack")
} else {
fmt.Println("\nDIFFERENT — one of the two walks is wrong")
}
return nil
}
func cmdDepth(args []string) error {
fs := flag.NewFlagSet("depth", flag.ContinueOnError)
n := fs.Int("n", 1000000, "how deep to nest")
iter := fs.Bool("iterative", false, "use the iterative walk instead")
if err := fs.Parse(args); err != nil {
return err
}
root := chain(*n)
var c metrics.Counter
start := time.Now()
var got int
if *iter {
got = WalkIterative(root, &c)
} else {
got = WalkRecursive(root, &c)
}
el := time.Since(start)
kind := "recursive"
if *iter {
kind = "iterative"
}
fmt.Printf("%s walk of a chain %d deep: %d items, %d folders, %s\n",
kind, *n, got, c.N(), el.Round(time.Millisecond))
fmt.Println(strings.Repeat("─", 60))
return nil
}
