打入门软件开发，斐波那契数列便是绕不过去的简单编程算法。
一个老生常谈的思路是递归，另外是循环，今天借此机会回顾并演示时间复杂度在编程中的重要性。
斐波那契 递归算法 1，1，2，3，5，8，13，21，34，55
递归算法的应用场景是：
func Fibonacci(n int) (r int) {
if n == 1 || n == 2 {
r = 1
return
} else {
return Fibonacci(n-1) + Fibonacci(n-2)
}
}
为什么能想到循环， 斐波那契数组也有循环的含义：
第n个数字是循环指针i从第1个数字移动到第n-2个数字时， 第n-2个数字pre+第n-1个数字next的和。
func Fibonacci2(n int) (r int) {
if n==1 || n==2 {
return 1
}
pre,next int :=1,1
for i:=0; i<=n-1-2; i++ {
tmp:= pre+next
pre = next
next = tmp
}
}
单元测试如下：
func TestFibonacci(t *testing.T) {
t.Logf("Fibonacci(1) = %d, Fibonacci2(1)= %d ", Fibonacci(1), Fibonacci2(1))
t.Logf("Fibonacci(3) = %d, Fibonacci2(3)= %d ", Fibonacci(3), Fibonacci2(3))
t.Logf("Fibonacci(8) = %d, Fibonacci2(8)= %d ", Fibonacci(8), Fibonacci2(8))
}
go test ./ -v
=== RUN TestFibonacci
m_test.go:8: Fibonacci(1) = 1, Fibonacci2(1)= 1
m_test.go:9: Fibonacci(3) = 2, Fibonacci2(3)= 2
m_test.go:10: Fibonacci(8) = 21, Fibonacci2(8)= 21
--- PASS: TestFibonacci (0.00s)
PASS
ok example.github.com/test 3.359s
(1) 函数调用存在压栈过程，会在线程栈（一般2M）上留下栈帧，斐波那契人递归算法：是函数自己调用自己，在终止条件后栈帧开始收敛，但是在此之前有可能已经撑爆线程栈。
栈帧中维持着函数调用所需要的各种信息，包括函数的入参、函数的局部变量、函数执行完成后下一步要执行的指令地址、寄存器信息等。
(2) 斐波那契递归调用存在重复计算，时间复杂度是O(2^n),随着n的增加，需要计算的次数陡然增大（业内称为指数型变化）。
f(n) = f(n-1)+f(n-2) // 1次计算
= f(n-2)+f(n-3)+f(n-3)+f(n-4) // 3次计算
= f(n-3)+f(n-4)+f(n-4)+f(n-5)+f(n-4)+f(n-5)+f(n-5)+f(n-6) // 7次计算
=......
= f(1)+...... // 2^n-1次计算
故为斐波那契递归时间复杂度为 O(2^n)
而我们的循环算法不存在以上问题， 第n个数字需要n -2次计算， 时间复杂度是O(n)
有些童鞋可能没意识到指数型的威力，举个例子， 斐波那契递归算法，第20个数字需要2^20次运算； 循环算法只要18次运算。
使用基准测试压测：
func BenchmarkF1(b *testing.B) {
for i := 1; i < b.N; i++ {
Fibonacci(20) // 时间复杂度 O(2^n)
}
}
func BenchmarkF2(b *testing.B) {
for i := 1; i < b.N; i++ {
Fibonacci2(20) // 时间复杂度 O(n)
}
}
go test -bench=. -benchmem ./
goos: darwin
goarch: amd64
pkg: example.github.com/test
cpu: Intel(R) Core(TM) i5-8257U CPU @ 1.40GHz
BenchmarkF1-8 55039 20740 ns/op 0 B/op 0 allocs/op
BenchmarkF2-8 196663548 6.080 ns/op 0 B/op 0 allocs/op
PASS
ok example.github.com/test 3.744s
单次执行效率相形见绌，甚至斐波那契递归n=50+ 不一定能计算出来。
ok, that'all 本次快速重温递归算法相比循环的两点劣势，这里面重要的常见时间复杂度变化曲线， 需要程序员必知必会。
https://adrianmejia.com/most-popular-algorithms-time-complexity-every-programmer-should-know-free-online-tutorial-course/
常规递归： 时间复杂度 O（2^n）, 而且存在爆栈的可能。
尾递归： 是对常规递归的优化，规避了爆栈的问题， 思路是规避持续压栈，利用编译器优化让整个递归过程只保持一个函数栈。
尾递归的核心表现： 函数运行到最后一步是否是调用自身，而不是在最后一行出现调用自身。
仔细体会：
// 这是常规递归
func diguiFunc(n int ) (r int) {
if n==1
return 1
return 1 + diguiFunc(n-1) // 递归调用函数自身时， 因为这一行不是直接返回值， 故上级堆栈不会释放，递归全过程会形成不断压栈，在终止时才开始出栈。
}
/*
f(4) = 1+ f(3)= 1+1+f(2)= 1+1+1+f(1)= 1+1+1+1 = 4
*/
// 这是尾递归
func tailFunc(n,pre int) (r int ) {
if n==1
return n
return tailFunc(n-1,1+ pre) // 开始调用此函数时，上级堆栈就会释放，递归全过程只会形成一个堆栈的占用。
}
/*
f(4,1) = f(3,1+1) = f(2,1+2) = f(1,1+3) =4
*/
故尾递归 能规避爆栈问题， 斐波那契尾递归的写法如下， 时间复杂度是O(n)， 跟循环是一样的。
func Fibonacii_tail(n int, pre int , next int) {
if n==1 || n==2 {
return next
}
return Fibonacii_tail(n-1,next, pre+next)
}
尾递归的实现思路是：
（1）使用递归体现循环，循环中要重复执行的代码体现在 尾递归调用的参数， 用调用自身的结果作为返回值
（2) 尾递归的终止参数是由外部驱动，在外部调用传值。