【新年快乐】CPS实现递归

公众号guangcity

发布于 2022-03-29 12:17:50

3530

发布于 2022-03-29 12:17:50

文章被收录于专栏：光城(guangcity)光城(guangcity)

CPS实现递归

1.普通递归

平时写递归，如下一个函数搞定。

func fib1(n int) int {
 if n <= 1 {
  return n
 }
 return fib1(n-1) + fib1(n-2)
}

2.闭包

假设在上述递归函数里面使用一些外部环境，例如：使用共享变量i，代码就变成下面这种。

func f() {
 var i = 0
 recursion(20, &i)
 fmt.Print(i)
}

func recursion(n int, p *int) int {
 (*p)++
 if n <= 1 {
  return n
 }
 return recursion(n-1, p) + recursion(n-2, p)
}

这种代码还得传递一个指针进去，非常不方便，这里我们可以变为闭包方式：

func fib2(n int) int {
 // 做一些共享变量事情
 var recursion func(n int) int
 // 跟外部环境形成闭包
 recursion = func(n int) int {
  if n <= 1 {
   return n
  }
  return recursion(n-1) + recursion(n-2)
 }
 return recursion(n)
}

3.CPS( Continuation-passing style)

这里直接饮用wiki上的解释：

Continuation passing style (CPS) is a style of writing programs in which the computation that happens after a function returns is packaged as a function and passed to that function instead where it is called directly.

In CPS, functions do not return. The computation that happens next is passed along as an argument in the form of a continuation function.

实现层面通常跟递归相关，例如：上述代码变为：

func fibonacci(n int, f func(a, b int) int) int {
 if n <= 1 {
  return f(n, 0)
 }
 return fibonacci(n-1, func(a, b int) int {
  return f(a+b, a)
 })
}

调用处：

fibonacci(6, func(a int, b int) int {
  fmt.Println("res is", a)
  return a
})

上述过程为f(6) = f(5) + f(4) + ... f(0)

最终会递归回来调用f(f(5), f(4)) = f(6)

上面比较绕感兴趣的可以拷贝代码自己打印过程输出。

4.其他补充

最后，补充一些variable scope相关内容。

嵌套递归

f := func() {
    f()
}

这种写法报错：

undefined: f

需要改为声明式:

var f func()
f = func() {
    f()
}

另一个例子是：

var m = map[int]string{
    1:  "one",
    21: "twenty-" + m[1],
}

这种也会报错undefined，同上述修改方法。

type identifier

通过type定义的内容可以直接嵌套。

例如：下面二叉树节点定义。

type Node struct {
    Left, Right *Node
}

此外还可以：

type Foo []Foo
type M map[int]M

https://www.zhihu.com/question/20259086

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2022-01-31，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

linux

本文分享自光城微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

linux

登录后参与评论

0 条评论

热度