深圳专业企业网站建,新品发布会的目的,网页制作软件免费吗,免费网站源码引言
“递归” 一词是比较专业的计算机术语#xff0c;在现实生活中#xff0c;有一个更可爱的词——“套娃”。如果把“递归算法”叫做“套娃算法”#xff0c;或许可以减少一些恐惧程度。
套娃是有限的#xff0c;同样#xff0c;递归也是有限的#xff0c;这和我们经…引言
“递归” 一词是比较专业的计算机术语在现实生活中有一个更可爱的词——“套娃”。如果把“递归算法”叫做“套娃算法”或许可以减少一些恐惧程度。
套娃是有限的同样递归也是有限的这和我们经常在影视作品中看到的“无限嵌套循环”是有很大区别的递归一定存在某个可以返回的节点或条件否则就会出现栈溢出错误StackOverflowError。
其实“套娃”这个词已经足以概括递归算法的本质就是函数本身调用自身直到找到一个可以返回的条件再层层返回。参考《盗梦空间》《明日边缘》等。
递归算法一定可以改写成非递归的实现方式迭代。本篇博客将会展示一个简单的递归算法案例并介绍评估递归算法时间复杂度的 Master公式。
一、案例数组中的最大值
正如前面所说递归算法一定可以改写成迭代方式那么也就是说递归也属于迭代只不过它每次迭代的内容和上一次都是一致的。
假设一个数组如何用递归的方式找到其中的最大值
分析我们可以使用一个类似二分的思路将数组层层二分左侧找一个值右侧找一个值二者取一个最大。反复这样的过程。
完整代码
public class RecursionGetMax {public static int getMax(int[] arr, int L, int R) {if (arr null || arr.length 0)throw new IllegalArgumentException(参数异常);if (arr.length 1)return arr[0];// arr[L..R]范围上只有一个数直接返回base caseif (L R)return arr[L];// 2个元素以上int mid L ((R - L) 1);// 递归取得区域最大int leftMax getMax(arr, L, mid);int rightMax getMax(arr, mid 1, R);return Math.max(leftMax, rightMax);}public static void main(String[] args) {int[] arr {1, 2, 3, 5, 22, 5, 221, 4, 6, 43, 6, 21, 1, 3, 3, 9};int max getMax(arr, 0, arr.length - 1);System.out.println(max);}
}注意这道题在设计时我们首先要有二分是思路基础然后我们思考要设计这样一个函数这个函数一定会接收一个需要查找的数组而仅仅传递数组的话那么就需要在方法中反复拷贝新数组显然空间复杂度太高因此不妨提供额外的两个指针方便我们选取数组上的数这样每次传递指针的值就可以避免每次传递截取的数组。
其次基础条件也是关键base case 是可以直接返回的条件即当 L R 时代表我们已经无法再继续二分因此可以直接返回这就是最终的返回节点如果没有这个条件那么递归将持续执行下去直到 StackOverflow 。因此在设计递归方法的时候一定要考虑好 base case。
二、递归的底层执行与逻辑分析方式
2.1 递归的底层实现
在系统中递归的实现是使用一个系统栈来完成的当方法执行到自身调用时系统会将“现场”保存到系统栈中擦除局部变量再重新跳到函数的开头继续执行。
例如一个数组 arr {4, 3, 8, 5, 7}初始 L 0R 4leftMax的返回值调用过程 2.2 逻辑分析方式
对于一个希望使用递归实现的方法我们并不需要每次都画出类似上图的栈结构来详细分析只需要画出逻辑递归图即可:
例如arr {5, 3, 4, 9}初始 L 0 R 3 三、递归算法的时间复杂度分析
由于递归算法是建立在一种不确定循环次数的情况下有点类似 do-while 循环因此在分析递归算法复杂度形式的时候只展开第一层的规模。
例如上述二分取值的方式就可以写成这样的时间消耗形式 T(N) a * T(N/b) T(N^d)其中 abd 都是常数 具体的值就是T(N) 2 * T(N/2) O(1) a 2, b 2, d 0。
Master 公式可以直接确定形如上面时间消耗形式的时间复杂度 如果 logb a d复杂度为O(N^d) 如果 logb a d复杂度为O(N^(logb a)) 如果 logb a d复杂度为O(N^d * logN) 其中logb a指的是以b为底 a 的对数。案例中的问题由于log2 d 1 0 因此时间复杂度就是 O(N^log2) O(N) 。
