尾调用/函数式编程初识以及go的相关

函数式编程

函数式编程: 函数式编程最常见的技术就是对一个集合做Map、Reduce和Filter操作，map对集合成员做了映射操作，生成新的集合；reduce就是降维操作，化整为零；filter顾名思义通过过滤器生成新的集合。

其特点是把函数当成变量来用

递归

递归算法在使用栈（stack，先进后出）来执行数据操作的时候是非常方便的，它比循环操作更快，并且代码的简洁性好。

递归带来的效率问题主要是函数调用带来的额外开销（函数的入栈出栈），以及栈容量的限制（次数太多可能会stack overflow）

递归算法：

优点：代码简洁、清晰，并且容易验证正确性。（如果你真的理解了算法的话，否则你更晕）
缺点：它的运行需要较多次数的函数调用，如果调用层数比较深，需要增加额外的堆栈处理（还有可能出现堆栈溢出的情况），比如参数传递需要压栈等操作，会对执行效率有一定影响。但是，对于某些问题，如果不使用递归，那将是极端难看的代码。

循环算法：

优点：速度快，结构简单。
缺点：并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话，最好使用循环。

系统栈（也叫核心栈、内核栈）是内存中属于操作系统空间的一块区域，其主要用途为： (1)保存中断现场，对于嵌套中断，被中断程序的现场信息依次压入系统栈，中断返回时逆序弹出； (2)保存操作系统子程序间相互调用的参数、返回值、返回点以及子程序(函数)的局部变量。
用户栈是用户进程空间中的一块区域，用于保存用户进程的子程序间相互调用的参数、返回值、返回点以及子程序(函数)的局部变量。
我们编写的递归程序属于用户程序，因此使用的是用户栈。

柯里化

也就是把接受多个参数的方法变换成接受第一个参数的方法，并且返回接受余下的参数而且返回结果的新方法。将多参数的函数转换成单参数的形式

例如:

def inc(x):
    def incx(y):
        return x+y
    return incx
 
inc2 = inc(2)
inc5 = inc(5)
 
print inc2(5) # 输出 7
print inc5(5) # 输出 10

尾调用/尾递归

某个函数的最后一步是调用另一个函数,这就是尾调用.

尾调用由于是函数的最后一步操作，所以不需要保留外层函数的调用记录，因为调用位置、内部变量等信息都不会再用到了，只要直接用内层函数的调用记录，取代外层函数的调用记录就可以了。这就叫做”尾调用优化”（Tail call optimization），即只保留内层函数的调用记录。如果所有函数都是尾调用，那么完全可以做到每次执行时，调用记录只有一项，这将大大节省内存。这就是”尾调用优化“的意义。

函数调用自身，称为递归。如果尾调用自身，就称为尾递归。如果其递归函数的第一个参数是需要返回的计算结果或者是中间变量.

递归非常耗费内存，因为需要同时保存成千上百个调用记录，很容易发生”栈溢出”错误（stack overflow）。但对于尾递归来说，由于只存在一个调用记录，所以永远不会发生”栈溢出”错误。

// 使用for循环执行
func factorialFor(n int) int {
	if n == 1 {
		return 1
	}
	res := 1
	for i := 2; i <= n; i++ {
		res = res * i
	}
	return res
}

// 递归, 内存占用O(n) 因为需要保存n个调用记录(中间结果)
func factorial(n int) int {
  if n == 1 {return 1}
  return n * factorial(n - 1)
}

// 尾递归, 理论上内存占用 O(1) 只需要保留一个调用记录, 实际上到go1.13都没有进行优化, 依旧是O(n) , 测试执行会比上面的快一点, 是因为函数调用尾递归调用中在管理stack frames上开销小一点. 
func factorial(n,total int) int{
    if n == 1 { return total}
    return factorial(n-1, n*total)
}

// 测试结果:
BenchmarkTailRecursive/For:-8         	68877586	        17.0 ns/op	       0 B/op	       0 allocs/op
BenchmarkTailRecursive/Rec:-8         	10000900	       119 ns/op	       0 B/op	       0 allocs/op
BenchmarkTailRecursive/Tail:-8        	11536790	       102 ns/op	       0 B/op	       0 allocs/op

似乎for循环更快. 因为减少了递归调用的压栈/出栈操作和函数调用的开销.

尾递归的实现，往往需要改写递归函数，确保最后一步只调用自身。做到这一点的方法，就是把所有用到的内部变量改写成函数的参数

可用通过外层再包装一层函数来隐藏尾递归优化的多出来的参数

1
2
3

func Factorial(n int) int{
    return factorial(n, 1)
}

也可以通过柯里化来做:

func currying(fn func, total int){
    return func(fn func, n int) {
        return fn(n,total)
    }
}

const Factorial = currying(factorial,1)

// 调用: Factorial(5)

当然如果像python那样支持默认参数值的,就可以通过默认参数设置默认值隐藏第二个参数了.

go的尾调用(tail calls)优化

当你要使用递归的时候，你需要意识到栈内存是一直增加的，直到遇到你设置好的 anchor 时，它的内存才开始下降。当我们说 Go 并没有优化递归操作时，我们需要承认一个事实，Go 并没有尝试着去优化栈内存无限增加这一操作, Go 没有 tail calls 进行任何优化, 调用栈并没有销毁。

// 汇编:
— prog list "TailRecursive" —
0018 (./main.go:17) TEXT TailRecursive+0(SB),$24-24

0019 (./main.go:17) MOVQ number+0(FP),CX

0020 (./main.go:17) LOCALS ,$0
0021 (./main.go:17) TYPE number+0(FP){int},$8
0022 (./main.go:17) TYPE product+8(FP){int},$8
0023 (./main.go:17) TYPE ~anon2+16(FP){int},$8

0024 (./main.go:19) MOVQ product+8(FP),AX
0025 (./main.go:19) ADDQ CX,AX

0026 (./main.go:21) CMPQ CX,$1
0027 (./main.go:21) JNE ,30

0028 (./main.go:23) MOVQ AX,~anon2+16(FP)
0029 (./main.go:23) RET ,

0030 (./main.go:26) MOVQ CX,BX
0031 (./main.go:26) DECQ ,BX

0032 (./main.go:26) MOVQ BX,(SP)
0033 (./main.go:26) MOVQ AX,8(SP) // 依旧不断地把参数压栈, 并未重复利用栈返回
0034 (./main.go:26) CALL ,TailRecursive+0(SB)

0035 (./main.go:26) MOVQ 16(SP),BX

0036 (./main.go:26) MOVQ BX,~anon2+16(FP)
0037 (./main.go:26) RET ,

// 通过chan去模拟尾递归, 这个调用栈会被优化, 因为每个goroutine执行完就返回了, 其会被销毁.
func RecursiveChannel(number int, product int, result chan int) {
    product = product + number
    if number == 1 {
        result <- product
        return
    }
    Go RecursiveChannel(number-1, product, result)
}

func main() {
    result := make(chan int)
    RecursiveChannel(4, 0, result)
    answer := <-result
    fmt.Printf("Recursive: %d\n", answer)
}

尾调用/函数式编程 初识以及go的相关