周而复始,往复循环,递归、尾递归算法与无限极层级结构的探究和使用(Golang1.18)

所有人都听过这样一个歌谣:从前有座山,山里有座庙,庙里有个和尚在讲故事:从前有座山。。。。,虽然这个歌谣并没有一个递归边界条件跳出循环,但无疑地,这是递归算法最朴素的落地实现,本次我们使用Golang1.18回溯递归与迭代算法的落地场景应用。

递归思想与实现

递归思想并非是鲜为人知的高级概念,只不过是一种相对普遍的逆向思维方式,这一点我们在:人理解迭代,神则体会递归,从电影艺术到Python代码实现神的逆向思维模式中已经探讨过,说白了就是一个函数直接或者间接的调用自己,就是递归,本文开篇和尚讲故事的例子中,和尚不停地把他自己和他所在的庙和山调用在自己的故事中,因此形成了一个往复循环的递归故事,但这个故事有个致命问题,那就是停不下来,只能不停地讲下去,所以一个正常的递归必须得有一个递归边界条件,用来跳出无限递归的循环:



package main  

import (  
    "fmt"  
)  

func story(n int) int {  
    if n 

这里我们声明了一个故事函数,参数为n,即讲n遍同样的故事,并且调用自己,每讲一次n减1,即减少一次讲故事总数,但如果我们不设置一个递归边界条件,那么函数就会无限递归下去,所以如果n小于等于0了,那么我们就结束这个故事:

➜  mydemo git:(master) ✗ go run "/Users/liuyue/wodfan/work/mydemo/tests.go"  
0

所以 if n

那么递归的底层是如何实现的呢?假设我们要针对n次故事做一个高斯求和:

package main  

import (  
    "fmt"  
)  

func story(n int) int {  
    if n 

程序输出:

➜  mydemo git:(master) ✗ go run "/Users/liuyue/wodfan/work/mydemo/tests.go"  
15

那么这一次递归高斯求和函数的底层实现应该是这样:

5+story(4)  
5+(4+ story(3))  
5+(4+(3+ story(2)))  
5+(4+(3+(2+ story(1))))  
5+(4+(3+(2+1)))  
15

当story函数每次被调用时,都会在内存中创建一个帧,来包含函数的局部变量和参数,对于递归函数,栈上可能同时存在多个函数帧。当每调用一次函数story(n)时,栈顶指针就会往栈顶移动一个位置,直到满足退出递归的条件(n

也就是说,内存栈会存储每一次递归的局部变量和参数,这也就是递归算法的性能被人们所诟病的原因,即不是自己调用自己而性能差,而是自己调用自己时,系统需要保存每次调用的值而性能差。

尾递归优化

尾递归相对传统的普通递归,其是一种特例。在尾递归中,先执行某部分的计算,然后开始调用递归,所以你可以得到当前的计算结果,而这个结果也将作为参数传入下一次递归。这也就是说函数调用出现在调用者函数的尾部,因为是尾部,所以其有一个优越于传统递归之处在于无需去保存任何局部变量,从内存消耗上,实现节约特性:



package main  

import (  
    "fmt"  
)

func tail_story(n int, save int) int {  

    if n 

程序返回:

➜  mydemo git:(master) ✗ go run "/Users/liuyue/wodfan/work/mydemo/tests.go"  
15

可以看到,求和结果和普通递归是一样的,但过程可不一样:

tail_story(5,0)  
tail_story(4,5)  
tail_story(3,9)  
tail_story(2,12)  
tail_story(1,14)  
tail_story(0,15)

因为尾递归通过参数将计算结果进行传递,递归过程中系统并不保存所有的计算结果,而是利用参数覆盖旧的结果,如此,就不会到处栈溢出等性能问题了。

递归应用场景

在实际工作中,我们当然不会使用递归讲故事或者只是为了计算高斯求和,大部分时间,递归算法会出现在迭代未知高度的层级结构中,即所谓的“无限极”分类问题:

package main  

import (  
    "fmt"  
)  

type cate struct {  
    id   int  
    name string  
    pid  int  
}  

func main() {  
    allCate := []cate{  
        cate{1, "计算机课程", 0},  
        cate{2, "美术课程", 0},  
        cate{3, "舞蹈课程", 0},  
        cate{4, "Golang", 1},  
        cate{5, "国画", 2},  
        cate{6, "芭蕾舞", 3},  
        cate{7, "Iris课程", 4},  
        cate{8, "工笔", 5},  
        cate{9, "形体", 6},  
    }  

    fmt.Println(allCate)  

}

程序输出:

[{1 计算机课程 0} {2 美术课程 0} {3 舞蹈课程 0} {4 Golang 1} {5 国画 2} {6 芭蕾舞 3} {7 Iris课程 4} {8 工笔 5} {9 形体 6}]

可以看到,结构体cate中使用pid来记录父分类,但展示的时候是平级结构,并非层级结构。

这里使用递归算法进行层级结构转换:

type Tree struct {  
    id   int  
    name string  
    pid  int  
    son  []Tree  
}

新增加一个Tree的结构体,新增一个子集的嵌套属性。

随后建立递归层级结构函数:

func CategoryTree(allCate []cate, pid int) []Tree {  
    var arr []Tree  
    for _, v := range allCate {  
        if pid == v.pid {  
            ctree := Tree{}  
            ctree.id = v.id  
            ctree.pid = v.pid  
            ctree.name = v.name  

            sonCate := CategoryTree(allCate, v.id)  

            ctree.son = sonCate  

            arr = append(arr, ctree)  
        }  
    }  
    return arr  
}

随后调用输出:

package main  

import (  
    "fmt"  
)  

type cate struct {  
    id   int  
    name string  
    pid  int  
}  

type Tree struct {  
    id   int  
    name string  
    pid  int  
    son  []Tree  
}  

func CategoryTree(allCate []cate, pid int) []Tree {  
    var arr []Tree  
    for _, v := range allCate {  
        if pid == v.pid {  
            ctree := Tree{}  
            ctree.id = v.id  
            ctree.pid = v.pid  
            ctree.name = v.name  

            sonCate := CategoryTree(allCate, v.id)  

            ctree.son = sonCate  

            arr = append(arr, ctree)  
        }  
    }  
    return arr  
}  

func main() {  
    allCate := []cate{  
        cate{1, "计算机课程", 0},  
        cate{2, "美术课程", 0},  
        cate{3, "舞蹈课程", 0},  
        cate{4, "Golang", 1},  
        cate{5, "国画", 2},  
        cate{6, "芭蕾舞", 3},  
        cate{7, "Iris课程", 4},  
        cate{8, "工笔", 5},  
        cate{9, "形体", 6},  
    }  

    arr := CategoryTree(allCate, 0)  
    fmt.Println(arr)  

}

程序返回:

[{1 计算机课程 0 [{4 Golang 1 [{7 Iris课程 4 []}]}]} {2 美术课程 0 [{5 国画 2 [{8 工笔 5 []}]}]} {3 舞蹈课程 0 [{6 芭蕾舞 3 [{9 形体 6 []}]}]}]

这里和Python版本的无限极分类:使用Python3.7+Django2.0.4配合vue.js2.0的组件递归来实现无限级分类(递归层级结构)有异曲同工之处,但很显然,使用结构体的Golang代码可读性更高。

结语

递归并非是刻板印象中的性能差又难懂的算法,正相反,它反而可以让代码更加简洁易懂,在程序中使用递归,可以更通俗、更直观的描述逻辑。

文章来源于互联网:周而复始,往复循环,递归、尾递归算法与无限极层级结构的探究和使用(Golang1.18)

THE END
分享
二维码