解决递归问题的四部曲（Java面试题）

什么是递归

改写说明

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

递归算法的深入解析
在上一节中深入探讨了递归的概念。我们可以进一步揭示了其两大核心特性

一个问题是可以通过分解为若干个具有相同解决思路的小问题来实现的。
在层层递归的过程中总会遇到一个不能再进一步分解而必须终止的状态（即所谓的终止条件）。
如果不存在这样的终止状态，则会导致无限递归下去而无法得到解答。

所以解答递归问题的关键在于我们第一步需要根据以上两个特点判断题目是否能用递归来解答。

经过判断之后,我们可以采用递归方法来解决问题;随后我们将深入探讨用递归解题的核心步骤(四个关键环节).

1. 先定义一个函数，明确这个函数的功能，由于递归的特点是问题和子问题都会调用函数自身，所以这个函数的功能一旦确定了,之后只要找寻问题与子问题的递归关系即可
2. 接下来寻找问题与子问题间的关系（即递推公式），这样由于问题与子问题具有相同解决思路，只要子问题调用步骤 1定义好的函数，问题即可解决。所谓的关系最好能用一个公式表示出来，比如 f(n) = n * f(n-)
   这样，如果暂时无法得出明