循环往复以至无穷,而实践和认识之每一循环的内容（周而复始,往复循环,递归、尾递归算法与无限极层级结构的探究和使用(Golang1.18)）

所有人都听过这样一个歌谣：从前有座山
  
  
  
  
  
  
  
  
  ，山里有座庙  
  
  
  
  
  
  
  
  
 ，庙里有个和尚在讲故事：从前有座山
  
  
  
  
  
  
  
  
  。  
  
  
  
  
  
  
  
  
 。
 


 


 


 


 


 


 


 


 


。
 
 
 
 
 
 
 
 
 。
 


 


 


 


 


 


 


 


 


，虽然这个歌谣并没有一个递归边界条件跳出循环
 
 
 
 
 
 
 
 
 ，但无疑地   
   
   
   
   
   
   
   
   
 ，这是递归算法最朴素的落地实现
 

 

 

 

 

 

 

 

 

，本次我们使用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"

所以 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代码可读性更高  
 
  
 
  
 
  
 
  
 
  
 
  
 
  
 
  
 
 。

结语

递归并非是刻板印象中的性能差又难懂的算法
 


 


 


 


 


 


 


 


 


，正相反
 
 
 
 
 
 
 
 
 ，它反而可以让代码更加简洁易懂   
   
   
   
   
   
   
   
   
 ，在程序中使用递归
 

 

 

 

 

 

 

 

 

，可以更通俗                   、更直观的描述逻辑


















。