递归（recursive)

迷宫问题(回溯)

递归的概念：

简单的说：递归就是函数/方法自己调用自己，每次调用时传入不同的变量。

递归有助于编程者解决复杂的问题，同时可以让代码变得简洁；

package main

import (
    "fmt"
)

func test(n int) {
    if n > 2 {
        n--
        test(n)
    }
    fmt.Println("n=", n)
}

func main() {
    test(4)
}

//函数调用时，使用栈进行`现场保存`；

//输出内容：
// n= 2
// n= 2
// n= 3

递归用于解决什么样的问题？

• 各种数学问题，如：八皇后问题，汉诺塔，阶乘问题，迷宫问题，球和篮子的问题(Google编程大赛)

• 将用栈解决的问题 ---> 使用递归解决，代码比较简洁；

递归需要遵守的重要原则：

• 1.执行一个函数时，就创建一个新的受保护的独立空间(新函数栈)；
• 2.函数的局部变量是独立的，不会相互影响；如果希望各个函数栈使用同一个数据，可以使用引用传递或全局变量；
• 3.递归必须向退出递归的条件逼近[程序员自己必须分析]，否则就是无限递归，死归了；
• 4.当一个函数执行完毕，或者遇到return，就会返回；遵守谁调用，就将结束返回给谁，同时当函数执行完毕或者返回时，该函数本身也会被系统销毁。

案例：迷宫问题

• 代码实现：

package main

import "fmt"

//编写一个函数，完成老鼠找路
//myMap *[8][7]int: 地图，保证是同一个地图，使用引用；
//i,j 表示对地图的哪个点进行测试：
func SetWay(myMap *[8][7]int, i int, j int) bool {
    //分析成什么情况下，算是找到了出路；
    //myMap[6][5] == 2
    if myMap[6][5] == 2 {
        return true
    } else {
        //说明要继续找：
        if myMap[i][j] == 0 { //如果这个点是可以探测的，而且没有探测过；

            //假设这个点是可以通的,但是需要探测； 上下左右；
            myMap[i][j] = 2
            // if SetWay(myMap, i-1, j) { //向上
            //  return true
            // } else if SetWay(myMap, i+1, j) { //向下
            //  return true
            // } else if SetWay(myMap, i, j-1) { //向左
            //  return true
            // } else if SetWay(myMap, i, j+1) { //向右
            //  return true
            // } else { // 死路
            //  myMap[i][j] = 3
            //  return false
            // }

            //换一个策略，下右上左
            if SetWay(myMap, i+1, j) { //向下
                return true
            } else if SetWay(myMap, i, j+1) { //向右
                return true
            } else if SetWay(myMap, i, j-1) { //向左
                return true
            } else if SetWay(myMap, i-1, j) { //向上
                return true
            } else { // 死路
                myMap[i][j] = 3
                return false
            }

        } else { //说明这个点不能探测，为1，是墙
            return false
        }
    }

}

func main() {
    //先创建一个二维数组，模拟迷宫；
    //规则：
    //1.如果元素的值为1，就是墙；
    //2.如果元素的值为0，是还没有走过的点；
    //3.如果元素的值为2，表示是通路；
    //4.如果元素的值为3，是走过的点，但是路不同；
    var myMap [8][7]int

    //先建墙
    //先把地图的最上和最下设置为1
    for i := 0; i < 7; i++ {
        myMap[0][i] = 1
        myMap[7][i] = 1
    }

    //先把地图的最左和最右设置为1
    for i := 0; i < 8; i++ {
        myMap[i][0] = 1
        myMap[i][6] = 1
    }
    myMap[3][1] = 1
    myMap[3][2] = 1

    //把路堵死,测试程序是否会退出；
    myMap[1][2] = 1
    myMap[2][2] = 1

    //输出地图：
    for i := 0; i < 8; i++ {
        for j := 0; j < 7; j++ {
            fmt.Print(myMap[i][j], " ")
        }
        fmt.Println()
    }

    //使用测试
    SetWay(&myMap, 1, 1)

    //输出地图：
    fmt.Println("探测完毕....")
    for i := 0; i < 8; i++ {
        for j := 0; j < 7; j++ {
            fmt.Print(myMap[i][j], " ")
        }
        fmt.Println()
    }
}

思考：如何找到最短路径？

• 方案一： 穷举所有策略，然后比较各种路径的长度；
• 方案二： ？？？