平时写递归,如下一个函数搞定。
func fib1(n int) int {
if n <= 1 {
return n
}
return fib1(n-1) + fib1(n-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)
}
这里直接饮用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)
上面比较绕 感兴趣的可以拷贝代码自己打印过程输出。
最后,补充一些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定义的内容可以直接嵌套。
例如:下面二叉树节点定义。
type Node struct {
Left, Right *Node
}
此外还可以:
type Foo []Foo
type M map[int]M
https://www.zhihu.com/question/20259086