recursion - 尝试将 slice 作为参数传递给递归函数时 slice 超出范围 (Go)

Question

我正在尝试将 slice 作为参数传递给递归函数。由于 slice 作为引用传递，我相信我传递给它的递归函数应该能够毫无问题地执行操作。我只使用 append()，因此应该不会遇到容量不足的 slice 问题吧？

package main

import "fmt"

func allPossiblePaths(arrGraph [8][8]bool, src int, dest int) [][]int {
    var visited []bool //a slice that marks if visited
    var path []int     //a slice to store a possible path
    var paths [][]int  //a slice to store all paths

    visited = make([]bool, 8) //set all nodes to unvisited

    dfs(arrGraph, src, dest, visited, path, paths)

    return paths

}

func dfs(myGraph [8][8]bool, src int, dest int, visited []bool, path []int, paths [][]int) {
    //add current node to path
    path = append(path, src)

    //mark current node as visited
    visited[src] = true

    //if the current node is the destination
    //print the path and return
    if src == dest {

        //make a copy of path slice
        buffer := make([]int, len(path))
        copy(buffer, path)

        //append the copy of path slice into the slice of paths
        paths = append(paths, buffer)

        fmt.Println(path) //Just for debugging purpose
        return
    }

    for i := 1; i <= 7; i++ { //loop through all nodes

        //if ith node is a neighbour of the current node and it is not visited
        if myGraph[src][i] && visited[i] == false {

            // call dfs on the current node
            dfs(myGraph, i, dest, visited, path, paths)

            //mark the current node as unvisited
            //so that we can other paths to the final destination
            visited[i] = false

            //re-slice the slice - get rid of the current node
            path = path[:len(path)-1]
        }

    }

}

func main() {
    var myGraph [8][8]bool //the graph

    //creating the graph
    myGraph[1] = [...]bool{false, false, true, true, false, false, true, false}
    myGraph[2] = [...]bool{false, true, false, true, false, true, false, false}
    myGraph[3] = [...]bool{false, true, true, false, true, false, true, false}
    myGraph[4] = [...]bool{false, false, false, true, false, false, true, false}
    myGraph[5] = [...]bool{false, false, true, false, false, false, true, false}
    myGraph[6] = [...]bool{false, true, false, true, true, false, false, true}
    myGraph[7] = [...]bool{false, false, false, false, false, false, true, false}

    fmt.Println(allPossiblePaths(myGraph, 1, 7))
}

OUTPUT:
[1 2 3 4 6 7]
[1 2 7]
[1 7]
[3 2 5 7]
[4 6 7]
panic: runtime error: slice bounds out of range
goroutine 1 [running]:
panic(0x4dc300, 0xc82000a0b0)
        /usr/local/opt/go/src/runtime/panic.go:481 +0x3e6
main.dfs(0x0, 0x1000001010000, 0x10001000100, 0x1000100010100, 0x1000001000000, 0x1000000010000, 0x100000101000100, 0x1000000000000, 0x3, 0x7, ...)
        /home/nitrous/src/test2b/main.go:52 +0x480
main.dfs(0x0, 0x1000001010000, 0x10001000100, 0x1000100010100, 0x1000001000000, 0x1000000010000, 0x100000101000100, 0x1000000000000, 0x1, 0x7, ...)
        /home/nitrous/src/test2b/main.go:45 +0x41f
main.allPossiblePaths(0x0, 0x1000001010000, 0x10001000100, 0x1000100010100, 0x1000001000000, 0x1000000010000, 0x100000101000100, 0x1000000000000, 0x1, 0x7, ...)
        /home/nitrous/src/test2b/main.go:12 +0x150
main.main()
        /home/nitrous/src/test2b/main.go:71 +0x423

预期输出:(使用全局变量而不是将变量传递给函数时实现)

[[1 2 3 4 6 7] [1 2 3 6 7] [1 2 5 6 7] [1 3 2 5 6 7] [1 3 4 6 7] [1 3 6 7] [1 6 7]]

知道我做错了什么吗？

Answer 1

错误消息准确说明了问题所在:

panic: runtime error: slice bounds out of range

由于您正在迭代调用相同的函数并重新 slice ，因此您需要每次检查是否达到 slice 容量范围，换句话说， slice 指针是否指向有效地址(索引)，否则您获取 超出范围错误 消息。

并且由于您正在进行递归迭代，通过每次减少路径长度，您必须检查 slice 索引是否在有效范围内。

//re-slice the slice - get rid of the current node
if len(path) > 0 {
       path = path[:len(path)-1]
}

https://play.golang.org/p/pX2TlAP-bp