所有人都听过这样一个歌谣：从前有座山，山里有座庙，庙里有个和尚在讲故事：从前有座山。。。。，虽然这个歌谣并没有一个递归边界条件跳出循环，但无疑地，这是递归算法最朴素的落地实现，本次我们使用Golang1.18回溯递归与迭代算法的落地场景应用。
递归思想与实现
递归思想并非是鲜为人知的高级概念，只不过是一种相对普遍的逆向思维方式，这一点我们在：人理解迭代，神则体会递归，从电影艺术到Python代码实现神的逆向思维模式中已经探讨过，说白了就是一个函数直接或者间接的调用自己，就是递归，本文开篇和尚讲故事的例子中，和尚不停地把他自己和他所在的庙和山调用在自己的故事中，因此形成了一个往复循环的递归故事，但这个故事有个致命问题，那就是停不下来，只能不停地讲下去，所以一个正常的递归必须得有一个递归边界条件，用来跳出无限递归的循环:
package main
import (
"fmt"
)
func story(n int) int {
if n <= 0 {
return 0
}
return story(n - 1)
}
func main() {
res := story(5)
fmt.Println(res)
}
这里我们声明了一个故事函数，参数为n，即讲n遍同样的故事，并且调用自己，每讲一次n减1，即减少一次讲故事总数，但如果我们不设置一个递归边界条件，那么函数就会无限递归下去，所以如果n小于等于0了，那么我们就结束这个故事：
➜ mydemo git:(master) ✗ go run "/Users/liuyue/wodfan/work/mydemo/tests.go"
0
所以 if n <= 0 就是递归边界条件。
那么递归的底层是如何实现的呢？假设我们要针对n次故事做一个高斯求和：
package main
import (
"fmt"
)
func story(n int) int {
if n <= 0 {
return 0
}
return n + story(n-1)
}
func main() {
res := story(5)
fmt.Println(res)
}
程序输出：
➜ 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<=0）之后再依次返回当前的结果直接，栈顶指针被压入栈底方向。
也就是说，内存栈会存储每一次递归的局部变量和参数，这也就是递归算法的性能被人们所诟病的原因，即不是自己调用自己而性能差，而是自己调用自己时，系统需要保存每次调用的值而性能差。
尾递归优化
尾递归相对传统的普通递归，其是一种特例。在尾递归中，先执行某部分的计算，然后开始调用递归，所以你可以得到当前的计算结果，而这个结果也将作为参数传入下一次递归。这也就是说函数调用出现在调用者函数的尾部，因为是尾部，所以其有一个优越于传统递归之处在于无需去保存任何局部变量，从内存消耗上，实现节约特性：
package main
import (
"fmt"
)
func tail_story(n int, save int) int {
if n <= 0 {
return save
}
return tail_story(n-1, save+n)
}
func main() {
save := 0
res := tail_story(5, save)
fmt.Println(res)
}
程序返回：
➜ 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代码可读性更高。
结语
递归并非是刻板印象中的性能差又难懂的算法，正相反，它反而可以让代码更加简洁易懂，在程序中使用递归，可以更通俗、更直观的描述逻辑。
文章评论