P09 斐波那契数列

小灰灰 2022-10-19 12:59 154阅读 0赞

斐波那契数列的第N位=(N-1)+(N-2)；开始仅知道第一位和第二位的值为0和1。求第N位的值的算法

> 0 1 2 3 5 8 13 21 34 55 … (n-2) (n-1) n

# 一、暴力递归 #

// 暴力递归 时间O(2^n) 空间O(1)
    func forceRecursion(n int) int { 
    	if n <= 1 {  // 第0、1位直接返回
    		return n
    	}
    	return forceRecursion(n-1) + forceRecursion(n-2)
    }

# 二、尾部递归 #

其实就是递归函数的返回不应携带运算.  
尾递归函数，部分高级语言编译器会进行优化，减少不必要的堆栈生成，使得程序栈维持固定的层数，不会出现栈溢出的情况。

func feibo(n, a1, a2 int){ 
    	if n == 0{ 
    		return a1
    	}
    	return feibo(n-1, a2, a1+a2)
    }

# 三、去重递归 #

func unrepeatRecursion(n int) int { 
    	array := make([]int, n+1)  // 数组从0开始，数列从1开始，下标以数列下标，所以需要增加1
    	return ()
    }
    func recursion(array []int, n int) int { 
    	if n <= 1 { 
    		return n
    	}
    	if array[n] != 0 {                 // 已经计算过，则返回
    		return array[n]
    	}
    	array[n] = recursion(array, n-1) + recursion(array, n-2)   // 没有计算过，则递归存储后返回
    	return array[n]
    }

# 四、双指针 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAwNTY1_size_16_color_FFFFFF_t_70_pic_center]

// 从下标位1的斐波那契数列，即没有第0位
    func doublePoint(index int) (curr int) { 
    	var left, right = 0, 1
    	if index <= 2 { 
    		return index - 1
    	}
    	for i := 3; i <= index; i++ {  // 从计算第三位开始
    		curr = left + right
    		left = right
    		right = curr
    	}
    	return
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAwNTY1_size_16_color_FFFFFF_t_70_pic_center]: /images/20221004/8f963ae0efd7447d960aed196ccd0ad0.png