每天一道算法题：递归求数组和的不同思路

约定不等于承诺〃 2022-10-27 02:49 199阅读 0赞

## 1、递归与循环 ##

针对刚开始接触的朋友，这里先对递归做一个简单的介绍，递归就是一个类似循环的思维，使用递归去解决问题主要是要做到**构造相似性**，那么怎么做到呢？主要有以下三点：

*  如果没有明显的相似性，需要主动构造
 *  不能相似的原因很可能是缺少参数
 *  递归与数学上的递推公式很类似

## 2、递归的思维过程 ##

分析：举个例子，这就像平时生活中需要办理什么材料证明一样，你去找相关部门，然后他说，你还没办xxx证明，然后让你去先办xxx证明，而受理xxx证明的部门又说，你还没办xxx证明，就像踢皮球一样，他踢给她，她又踢给它，**当你办好他们说的最后一个部门的证明时，你还得拿这个证明往前去办理其他证明，回去办其他证明的过程就叫做——回调函数**。现在，假设我们有一个数组,我们要求他的和，那么按照上面我们分析的递归的思想，我们应该这么做呢？

int arr[] = { 1,2,3,4,5};

在上面的分析中我们说过，递归就像踢皮球  
\[.+\[.+\[.+\[…\]\]\]\]：它们每一个都只想执行a+b的操作，而不是a+b+c…+n,就是说我只求第一项+后面向的和，后面的数的和由回调函数返回。拿前面的例子来说，上面的每一个点就像一个部门，想等后面的手续全齐了它才能受理，我们带入到函数中，它一直循环，直到碰到出口，最后一个函数结束，开始执行回调，将得到的结果返回给前面的函数（部门），然后最终结果由最开始的函数返回；

通过本文的学习，相信对您了解递归有一定的帮助！（新手朋友最好能把下面的6种思路独立写一遍，这样对您学习递归的帮助更大）

## 3、今日算法：递归求数组和 ##

### 3.1、思路1：从begin开始到end结束的元素和 ###

public static int f1(int arr[],int begin){ 
            //递归结束条件：开始下标等于数组的长度
            if(begin<arr.length){ 
                //踢皮球 [.+[.+[........]]]
                //当前函数都只想求两个数的和，都先往后抛，等拿到结果我再计算两个数的和
               int x = f1(arr,begin+1);
                return x + arr[begin];//一个函数只会执行一次，return会结束程序
            }
            return 0;
        }

### 3.2、思路2：从end末尾到begin顶端的元素和 ###

public static int f2(int arr[],int begin,int end){ 
            //归结束条件：末尾下标<顶端下标
            if(end<begin) return 0;
            //在f1的基础上颠倒顺序,一样的踢皮球
            //[[[...]+.]+.]
            int x = f2(arr,begin,end-1);
            return x+arr[end];
        }

### 3.3、思路3：从起始坐标begin到起始坐标+1的元素和（顺序累加） ###

public static int f3(int arr[],int begin,int beginauto){ 
            //递归条件：当begin==数组的长度时，结束递归
            if(begin==arr.length) return 0;
            //这里形容的话更像是一个左开右闭的区间[0,1)，和取0,然后往后递归
            //[1,2),[2,3)...[4,5);每次递归返回该区间值
    // System.out.printf("begin=%d,beginauto=%d\n",begin,beginauto);
            int x = f3(arr,begin+1,beginauto+1);
            return x+arr[begin];
        }

### 3.4、思路4：从末尾坐标end到末尾坐标-1的minus\_1的元素和 ###

public static int f4(int arr[],int end,int minus_1){ 
            //递归条件：当end<0时，会造成下标越界，故结束递归
            if(end<0) return 0;
            //这里形容的话更像是一个左闭右开的区间(3,4]，和取4,然后往前递归，知道右开的值为0
            //(3,4],(2,3]...(-1,0];每次递归返回该区间值
            int x = f4(arr,end-1,minus_1-1);
            return x + arr[end];
        }

### 3.5、思路5：二分法，将arr分成左右两部分分别求值进行+运算 ###

public static int f5(int arr[],int begin,int end){ 
            int middle = (begin + end) / 2;
            //针对left部分，如果begin>end，结束递归
            if (begin > end)
                return 0;
            //针对right部分,end是不变的，无论右部分元素是奇还是偶，middle都会一直向右靠近，直到==end
            if (begin == end)
                return arr[end];
    
            return f5(arr, begin, middle) + f5(arr, middle + 1, end);
        }

### 3.6、思路6：两端相向移动法，让起始坐标和末尾坐标相向移动并求和 ###

public static int f6(int arr[],int begin,int end){ 
            if(begin==end) return arr[end];
            if(end-begin==1) return arr[begin]+arr[end];
            int x = f6(arr,begin+1,end-1);
            return x + arr[begin]+arr[end];
        }

## 4、测试代码 ##

public static void main(String[] args) { 
            int arr[] = { 1,3,5,7,15};
            //f1和f2思路一样，但相互颠倒顺序
            int sum1 = f1(arr,0);//从0++到end
            int sum2 = f2(arr,0,arr.length-1);//从end--到0
    
            //f3和f4思路一样，但相互颠倒顺序
            int sum3 = f3(arr,0,1);//按顺序求和，从[0,1)到[4,5);
            int sum4 = f4(arr,4,3);//按顺序求和，从(3,4]到(-1,0];
    
            //二分法
            int sum5 = f5(arr,0,arr.length-1);
            //两端靠近法
            int sum6 = f6(arr,0,arr.length-1);
            System.out.println(sum1);
            System.out.println(sum2);
            System.out.println(sum3);
            System.out.println(sum4);
            System.out.println(sum5);
            System.out.println(sum6);
        }

### 4.1、运行结果 ###

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ3OTUzODU1_size_16_color_FFFFFF_t_70]: /images/20221024/e43edb9d9fe14fafa38ab8e3f5a182df.png