Golang中的结构上的递归函数

Question

I have the following code to organise *Widget structs into a hierarchy. Parent() returns the widget with an ID of the caller's parentID. The hierarchy can be up to 4 or 5 levels deep.

type Widget struct {
  ID int64
  ParentID int64
}

func (w *Widget) Parent() *Widget {
  // Returns the widget with an ID of w.ParentID
}

What I want to achieve is a function which aggregates the parent, as well as the parent's parent etc. to the top of the hierarchy, and returns a slice of all of the parent IDs. As I don't know the depth of the hierarchy, I think I need some sort of programmatic recursion to get the parent of each parent, which would do something like the following:

func (w *Widget) AllParents() []*Widget {
  var parentWidgets []*Widget
  x := w.Parent()
  parentWidgets = append(parentWidgets, x)
  y := x.Parent()
  parentWidgets = append(parentWidgets, y)
  ...
  return parentWidgets
}

Is there a more idiomatic way of achieving this?

Answer 1

You just need to step higher and higher in the hierarchy until you reach the root. Assuming Widget.Parent() returns nil if the Widget is the "root" (meaning it has no parent):

Iterative solution

Here is the solution with a simple for loop:

func (w *Widget) AllParents() []*Widget {
    var ws []*Widget
    for parent := w.Parent(); parent != nil; parent = parent.Parent() {
        ws = append(ws, parent)
    }
    return ws
}

This method will return nil if called on the "root" (zero value for all slice types). In other cases, it will return the "path" from the direct parent leading to the "root".

Here's a little test program. It creates a root widget with ID = 0, a child with ID = 1 and a "grandchild" with ID = 2, and prints AllParents() called on each. To implement Widget.Parent(), I used a simple "widget registry" map.

Result as expected:

Parents of 0:
Parents of 1: 0
Parents of 2: 1 0

Try it on the Go Playground.

var wreg = map[int64]*Widget{}

func (w *Widget) Parent() *Widget {
    // Returns the widget with an ID of w.ParentID
    return wreg[w.ParentID]
}

func main() {
    w := &Widget{0, -1}
    wreg[w.ID] = w
    w2 := &Widget{1, 0}
    wreg[w2.ID] = w2
    w3 := &Widget{2, 1}
    wreg[w3.ID] = w3

    printParents(w)
    printParents(w2)
    printParents(w3)
}

func printParents(w *Widget) {
    fmt.Printf("Parents of %d:", w.ID)
    for _, w := range w.AllParents() {
        fmt.Print(" ", w.ID)
    }
    fmt.Println()
}

Recursive solution

Of course it can be solved using recursion too:

func (w *Widget) AllParents() []*Widget {
    if parent := w.Parent(); parent == nil {
        return nil
    } else {
        return append(parent.AllParents(), parent)
    }
}

This solution returns the "path" from the root leading to the direct parent.

Running the above test program with this implementation, output is:

Parents of 0:
Parents of 1: 0
Parents of 2: 0 1

Try this on the Go Playground.