一篇看懂递归的套路解题法
所谓递归,不过是将一个复杂问题分解为一个更小的问题进行求解,在这里我们不再扯太多犊子了,网上有太多递归的介绍让人眼花缭乱摸不着头脑,我们直接开始讲解递归的解体思路。
这一步也就是网上所谓的递归出口,但是个人认为递归出口不太能很好的描述这个意思,其实本质就是求出来最简单的问题最后一项并将其返回,一般这个项也就是返回一个1或者0之类的东西。不说废话,举个例子。
计算数组arr[index.... n)范围里的数字和
传入一个下标index,求从index开始到最后一项的和,我们直接开始求这个问题的最后一项的值,毫无疑问,数组的最后一项的再后一项的值为0,也就是当index等于我们的数组长度时的值为0。(防止新手看不懂,这里的数组长度是指从1开始加的值,举个例子一个数组下标0,1,2,其实数出来的长度为3)
因此我们写好求解最基本问题并将其返回的这段代码
if(index == arr.length){
return 0;
}
ok开始我们的第二步
第二步:使用递归函数本身并加上一些操作实现功能需求
这里就是我们递归最关键的一点,我认为我们在这个地方有一个大坑,就是过度的去关注我们在写一个递归,从而把自己绕进去。打个比方,就是不用老是觉得A函数在调用A函数自己,其实我们把他看作A函数在调用B函数来解决问题就好了。ok说了这么多,直接开始3步走。
-
再次写一遍递归函数,但是注意可变参数要变化,一般就是下几个或加几(类比我们for循环要i++或i--一样)
-
调用递归函数之后再进行一些操作(这个要自己想)
-
将上面代码return
还是上面的例子,思考一下,是不是累加就是将当前下标的值加上下一个下标的值,所以就是
return arr[index] + sum(arr, index + 1);
总结一下:
public static void sum(int[] arr,int index){
if(index == arr.length)
return 0;
return arr[index] + sum(arr, index + 1);
}