Demonstrating recursion vs. iteration

recursive_vs_iterative_dfs.go

package main

import (
	"fmt"
	"time"
)

type TreeNode struct {
	Goal     bool
	Children map[string]*TreeNode
}

func makeTree(root *TreeNode, width int, depth int, goal_at_leaf bool) {
	if depth == 0 {
		root.Goal = goal_at_leaf
		return
	}

	for i := 0; i < width; i++ {
		key := fmt.Sprintf("child%v", i)
		newNode := &TreeNode{
			Goal:     false,
			Children: make(map[string]*TreeNode),
		}
		root.Children[key] = newNode
		makeTree(newNode, width, depth-1, goal_at_leaf)
	}
}

func recursive(root *TreeNode, visited map[*TreeNode]struct{}) *TreeNode {
	if _, ok := visited[root]; ok {
		return nil
	}
	visited[root] = struct{}{}
	if root.Goal {
		return root
	}
	for _, v := range root.Children {
		// Don't visit a second time.
		if _, ok := visited[v]; ok {
			continue
		}
		goal := recursive(v, visited)
		if goal != nil {
			return goal
		}
	}
	return nil
}

func start_recursive(root *TreeNode) *TreeNode {
	visited := make(map[*TreeNode]struct{})
	return recursive(root, visited)
}

func iterative(root *TreeNode) *TreeNode {
	pending := []*TreeNode{root}
	visited := make(map[*TreeNode]struct{})

	for len(pending) > 0 {
		// Pop next node to visit
		curr := pending[len(pending)-1]
		pending = pending[:len(pending)-1]

		if _, ok := visited[curr]; ok {
			continue
		}
		visited[curr] = struct{}{}
		if curr.Goal {
			return curr
		}

		for _, v := range curr.Children {
			if _, ok := visited[v]; ok {
				continue
			}
			pending = append(pending, v)
		}
	}
	return nil
}

func main() {
	testCases := []struct {
		width int
		depth int
		goal  bool
	}{
		{10, 5, true},
		{10, 5, false},
		{20, 5, true},
		{20, 5, false},
	}

	for _, tc := range testCases {
		root := &TreeNode{
			Goal:     false,
			Children: make(map[string]*TreeNode),
		}
		fmt.Printf("#####################\nWidth %v, Depth %v, Goal %v\n",
			tc.width, tc.depth, tc.goal)
		makeTree(root, tc.width, tc.depth, tc.goal)
		fmt.Printf("Constructed...\n")

		// Warm up the cache
		start_recursive(root)
		iterative(root)

		fmt.Printf("Sampling...\n")

		for sample := 0; sample < 5; sample++ {
			start_time := time.Now()
			start_recursive(root)
			end_time := time.Now()
			fmt.Printf("recursive %v\n", end_time.Sub(start_time))
		}

		for sample := 0; sample < 5; sample++ {
			start_time := time.Now()
			iterative(root)
			end_time := time.Now()
			fmt.Printf("iterative %v\n", end_time.Sub(start_time))
		}

	}

}