Java基础-基础语法-递归 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. 一个问题可以分解成具有相同解决思路的子问题，子子问题，换句话说这些问题都能调用同一个函数
1. 经过层层分解的子问题最后一定是有一个不能再分解的固定值的（即终止条件）,如果没有的话,就无穷无尽地分解子问题了，问题显然是无解的。

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

递归算法通用解决思路:

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

递归总结
形成递归条件为自我调用且有完成状态。
循环能干的事,递归都能干; 递归能干的循环不一定能干。
工作开发过程中,能用循环解决的,尽量不适用递归.因为递归使用栈内存处理数据,可能抛出栈溢出异常(StackOverflowException)。
【Java基础-基础语法-递归】递归扩展
一些常见的使用递归的问题：简单递归