什么是递归

什么是递归_03

什么是递归

递归是函数调用时的一个概念，通俗点讲就是：方法自己调用自己。

怎么使用

首先使用递归的时候，需要满足两个条件：

1. 递归出口（终止递归的条件）
2. 递归表达式
   技巧：将问题切割成两个部分（1和整体的思想），找到递归表达式即可。

• 举例：
  问题：求1到100以内的和
  for 循环来写

     int sum = 0;
     for (int i = 1; i <= 100; i++) {
            sum = sum + i;
        }

递归思想

先将问题切割成两部分，通过公式我们可以看出：1+2+3+…+100可以等价于：(1+2+3+…+99)+100。同时可以将1+2+3+…+99在看成一个整体，而这个整体要做的事情和我们初始化（求和）相同。
利用公式化的思想，上面的分析可以写成：sun(n-1)+n样式的表达式。
表达式已经有了，那么递归出口呢？继续分析我们发现：

1. 如果n=1，那么返回值为1.
2. 如果n=2，那么返回值为3.
3. 如果n=3，那么返回值为6.

因此递归出口可以取：n=1时的返回值1。
综上，用代码表示如下：（递归写法）

    public static int sum(int n) {
            if (n == 1) {
                return 1;
            } else {
                return sum(n - 1) + n;
            }
        }