一篇看懂递归的套路解题法

递归

所谓递归,不过是将一个复杂问题分解为一个更小的问题进行求解,在这里我们不再扯太多犊子了,网上有太多递归的介绍让人眼花缭乱摸不着头脑,我们直接开始讲解递归的解体思路。

第一步:求解最基本问题并将其返回

这一步也就是网上所谓的递归出口,但是个人认为递归出口不太能很好的描述这个意思,其实本质就是求出来最简单的问题最后一项并将其返回,一般这个项也就是返回一个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);
}

 

热门相关:无量真仙   修仙界最后的单纯   最强反套路系统   战神   豪门重生盛世闲女