Why does the recursion work this way in Go?-CodePudding

I'm learning Go to prepare for a coding interview, and there's a leetcode question for tree traversal. It works with recursion in Python, but Golang behaves differently.

I notice the elements in the res slice gets cleared one by one when every call stack is popped.

The original question is

The result should be [1,3,5,6,2,4], and it was returned correctly in Python, but the following Go code returns []

    /**
     * Definition for a Node.
     * type Node struct {
     *     Val int
     *     Children []*Node
     * }
     */
    
    func preorder(root *Node) []int {
        res := []int{}
    
        traverse(root, res)
    
        return res
    }
    
    func traverse(root *Node, res []int){
        if root == nil{
            return
        }
    
        res = append(res, root.Val)
    
        for _, n := range root.Children{
            traverse(n, res)
        }
        // the last element is removed from the slice every time when the code execution reaches here 
    }

------------------------------------- updates --------------------------------------

Thanks for all your answers, now I think I have a better understanding of how slice works in Go

The following code works for me now:

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func preorder(root *Node) []int {
    res := []int{}

    res = traverse(root, res)

    return res
}

func traverse(root *Node, res []int) []int{
    if root == nil{
        return res
    }

    res = append(res, root.Val)

    for _, n := range root.Children{
        res = traverse(n, res)
    }

    return res
}

CodePudding user response：

you can consider passing the res as a pointer *[]int instead so that the values get updated to the same slice else you are just passing a copy of it.

CodePudding user response：

In your terminating case, you're not returning the accumulator:

if root == nil{
  return
}

But...

I would use a closure so as to avoid cloning the slice on every recursive call (Go passes by value):

type Node struct {
    Val      int
    Children []*Node
}

func preorder(root *Node) (res []int) {
    var traverse func(*Node)

    traverse = func(root *Node) {
        if root != nil {

            res = append(res, root.Val)

            for _, n := range root.Children {
                traverse(n)
            }
        }
    }

    traverse(root)

    return res
}