Java基础-基础语法-递归

Java工程师知识树 / Java基础

---

什么是递归？

简单地说，就是如果在函数中存在着调用函数本身的情况，这种现象就叫递归。

以阶乘函数为例,如下, 在 factorial 函数中存在着 factorial(n - 1) 的调用，所以此函数是递归函数.

public int factorial(int n) {
    if (n < =1) {
        return 1;
    }
    return n * factorial(n - 1)
}

递归思想

递归思想

递归的阶段

递归的阶段

分析递归方法在JVM的内存结构

public static int jieCheng(int n) {
    if (n <=1) {
        return 1;
    }
    return n * jieCheng(n - 1);
}

public static void main(String[] args) {
    System.out.println(jieCheng(5));
}

执行以上代码递归内存结构图如下

递归内存结构图

递归函数特点：

• 1. 一个问题可以分解成具有相同解决思路的子问题，子子问题，换句话说这些问题都能调用同一个函数
• 2. 经过层层分解的子问题最后一定是有一个不能再分解的固定值的（即终止条件）,如果没有的话,就无穷无尽地分解子问题了，问题显然是无解的。

一句话总结递归：自我调用且有完成状态。

递归算法通用解决思路:

• 1. 先定义一个函数，明确这个函数的功能，由于递归的特点是问题和子问题都会调用函数自身，所以这个函数的功能一旦确定了， 之后只要找寻问题与子问题的递归关系即可
• 2. 接下来寻找问题与子问题间的关系（即递推公式），这样由于问题与子问题具有相同解决思路，只要子问题调用步骤 1 定义好的函数，问题即可解决。
     所谓的关系最好能用一个公式表示出来，比如 f(n) = n * f(n-1) 这样，如果暂时无法得出明确的公式，用伪代码表示也是可以的, 发现递推关系后，要寻找最终不可再分解的子问题的解，即（临界条件），确保子问题不会无限分解下去。
     由于第一步我们已经定义了这个函数的功能，所以当问题拆分成子问题时，子问题可以调用步骤 1 定义的函数，符合递归的条件（函数里调用自身）
• 3. 将第二步的递推公式用代码表示出来补充到步骤 1 定义的函数中
• 4. 最后也是很关键的一步，根据问题与子问题的关系，推导出时间复杂度,如果发现递归时间复杂度不可接受，则需转换思路对其进行改造，看下是否有更靠谱的解法，不是所有的递归都是可取的。

递归总结

形成递归条件为自我调用且有完成状态。
循环能干的事,递归都能干;递归能干的循环不一定能干。
工作开发过程中,能用循环解决的,尽量不适用递归.因为递归使用栈内存处理数据,可能抛出栈溢出异常(StackOverflowException)。

递归扩展
一些常见的使用递归的问题：简单递归