递归基础思想

朱雀 2022-05-26 13:55 256阅读 0赞

有个朋友刚刚在学习java，刚学了一个月，他虽然脑袋很大（不是针对所有人，只是针对他），但是说自己总是在解题的时候找不到思路。他在学习时遇到了几道关于递归的小题，今天简单聊一下关于递归的思路。

![1][]

上面是朋友发过来的图片，就这几道题简单谈一下递归从哪里入手。

先介绍一下递归，百度百科是这样解释的：程序调用自身的编程技巧称为递归（ recursion）。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

从上面的话我们可以看出，递归其实就是将大的问题分解成小的问题，并且这个子问题的解决方法和大问题的解决方法一样。

其中必须满足以下条件：  
1.必要条件必须要有终止条件  
2.子问题要更接近终止条件

以上图第一个例子说明一下：

**编写代码，完成1+2+3+4+…+100输出结果**:

这里以1加到5为例子

public static void main(String args[]) {
            System.out.println(result(5));
        }
    
        public static int result(int i){
            int sum;
            if (i == 1) return 1;
            else
                sum = i + result(i - 1);
                System.out.println("i是："+i+"------sum是："+sum);
            return sum;
        }

从代码来看是这样一个调用过程：

result(5)
    5+result(4)
    5+(4+result(3))
    5+(4+(3+result(2)))
    5+(4+(3+(2+result(1))))

展开成数字来看：

(5+(4+(3+(2+(1))))）
    (5+(4+(3+(2+1)))）
    (5+(4+(3+3))）
    (5+(4+6)）
    (5+10）

这时我们在回头看递归的满足条件：  
条件一：终止数字1（✔️）  
条件二：每次减1来接近终止数字（✔️）

[1]: /images/20220526/0d22fa66f5764f7fb5d5db58552e1c18.png