go语言使用递归与循环两种方式计算斐波那契数列

　　题目
　　给定一个正整数n计算出对应斐波那契数列对应的值使用递归方式借助切片用循环方式
　　说明:递归函数的时间复杂度是Tn=O(f(n)),它表示随问题规模n的增大，算法的执行时间增长率和f (n)增长率成正比，这称作算法的渐进时间复杂度。 为了解决效率问题，可以将递归方式转换为循环方式，达到以空间换时间的效果。循环方式计算斐波拉契数列对应值时间复杂度仅O(n)。
　　代码实现
　　递归方式计算package main  import ( 	＂fmt＂ 	＂time＂ )  /* 用递归方式计算斐波拉契数列 	*/  func fibonacci(n int) (res int) { 	if n<=1 { 		// n==0或n==1时，返回值为1 		return 1 	} else { 		// n>=2时，结果需要递归计算前2位的值 		return fibonacci(n-1) + fibonacci(n-2) 	} }  func main()  { 	// 记录开始时间 	start := time.Now().Unix() 	 	num := 52 	// 给定一个值,计算结果 	fmt.Println(fibonacci(num)) 	 	// 打印总耗时 	fmt.Println(＂total(s):＂,time.Now().Unix() - start) }
　　循环方式计算package main  import ( 	＂fmt＂ 	＂time＂ )  /* 以切片作为存储，用循环方式计算斐波拉契数列 相比递归方式，以空间换时间 	*/   func fibonacci(n int) []int { 	// 定义切片，用于保存结果 	var numList []int 	res := 0 	for i:=0;i<=n;i++ { 		if i==0 { 			numList = append(numList,1) 		} else if i==1 { 			numList = append(numList,1) 		} else { 			// 如果是n>=2，每个当前的值，等于切片的前2位之和 			res = numList[i-1] + numList[i-2] 			numList = append(numList,res) 		} 	} 	return numList }  func main()  {  	// 定义切片，用于保存结果 	var numList []int 	// 记录开始时间 	start := time.Now().Unix() 	 	num := 52 	// 给定一个值,计算结果 	numList = fibonacci(num) 	fmt.Println(numList[num])  	// 打印总耗时 	fmt.Println(＂total(s):＂,time.Now().Unix() - start) }
　　结果比较
　　用mackbookpro i7 2.7GHZ笔记本进行测试，结果如下:
　　n
　　n=40
　　n=45
　　n=50
　　n=52
　　n=80
　　递归(秒)
　　0
　　5
　　59
　　163
　　>600
　　循环(秒)
　　0
　　0
　　0
　　0
　　0
　　备注: 当n=80时，由于测试等待时间过长，强制中断了执行。
　　从测试结果看出，当n逐渐增大，递归方式计算斐波拉契数列的时间复杂性急剧增加。当n值较大时可以考虑用循环方式代替。
　　类似的方式也可以用于，求阶乘、遍历目录、汉诺塔等问题的解决。在后期的文章中，我将这些内容进行补充，敬请期待，谢谢。