递归算法分析-最简单的例子

概述

递归算法在算法设计中,是一种比较难以理解的算法存在,感觉递归算法无限套娃,最终居然也能返回正确结果,对于初入坑的童靴是一个神一般的存在。本文通过对递归算法的一个例子,从最简单的例子中,逐步撕开其神秘面纱。

最简单的题目

给你一个整数数组,要求返回这个数组中的最大值

要求使用递归算法

如:数组{1,44,-9,10,18,6,22}最大值为44

分析

相信拿到这个简单题目的同学一定很开心,这不是最简单的一道题吗?遍历数组,保存最大值即可完成。但如果是要求使用递归算法呢?那该如何做解?

递归一般套路都是,将大问题分解成小一点的问题,再继续分解成更小的问题,直到这个最小的问题我们是知道答案的,也就是递归的边界

那在这道题中,我们该如何去分解这个场景呢?

我们可以这么想,要想知道n个整数数组的最大值,我们是不是可以分解成n-1个整数数组的最大值和第n个数值比较,取出最大值。要想知道n-1个整数数组的最大值,就可以分解成n-2个整数数组的最大值和第n-1个数值比较,依此套娃下去,直到n=1的时候,我们是可以直到n=1的最大值就是他本身,然后再顺着回去,原来怎么套,回去就怎么解

代码(golang)

通过以上的分析,我们可以得出以下的代码内容,详细思路看代码注解

func main() {
	s:= []int{1,44,-9,10,18,6,22}
	fmt.Println(findMaxInt(s))
}
func findMaxInt(s []int) int{
	//递归的边界,当整个数组只有一个元素时
	if len(s)==1{
		return s[0]
	}
	//求解数组长度为n-1时的情况
		return max(findMaxInt(s[0:len(s)-1]),s[len(s)-1])

}
//返回两个整数的最大值
func max(i,j int)int{
	if i>j{
		return i
	}else{
		return j
	}
}

强烈不理解的童鞋打开调试,跟着调试一起走,非常清晰可以看到一个栈,这是一个先入后出的队列。

复杂度分析

时间复杂度

递归的时间复杂度跟递归调用次数相关,分析代码可知,我们一共调用了n次,第一次是求有n个数组,第二次是求含有n-1个数组…直到边界条件n=1,所以一共调用了n次,时间复杂度为O(n)。

空间复杂度

递归的空间复杂度跟递归堆栈有关,这里最大需要用到n个堆栈,每一次调用,都需要压一次栈,所以空间复杂度为O(n)

使用迭代算法

这道题如果使用迭代算法,时间复杂度一样,空间复杂度可以优化为O(1)

具体代码如下

func main() {
   s:= []int{1,44,-9,10,18,6,22}
   //初始化答案为0
   ans :=0
   for _,v:=range s{
      if v>ans{
         ans=v
      }
   }
   fmt.Println(ans)
}

其实迭代算法也是将问题缩小的过程,只不过求解方向跟递归正好相反。迭代时先计算只有1个整数的数组情况,然后计算2个,3个。。。到n个,这其中就不需要使用栈,我们可以使用一个临时变量来保存当前的最大值,最后返回最大值即可,空间复杂度为O(1),大大低于递归算法。

总结

这道题使用的递归算法求解显然没有迭代的方式来得更加优秀,主要是用来展示下递归是如何使用和工作的,递归主要开销是来源于栈空间的,如果栈空间满了,则程序就溢出了,建议最好使用迭代方式,可以自主控制队列容量大小。这类的求最值,我们可以用DP(动态规划)的方式来进行分析,原理基本是一致的。

你可能感兴趣的