优雅的实现递归

有些时候写递归比循环的方法更简便一些，只是如果随便写个递归，勉强完成了功能，但是代码是有些别扭，比如方法太长，没有明确的顺序，想到哪写到哪。

实际上递归是有比较经典的写法，可以让代码看起来更易读。

什么是递归

递归的定义：一种计算过程，如果其中每一步都要用到前一步或前几步的结果，称为递归的

我们知道递归要满足两个条件：

• 必须有一个终止计算的规则
• 每次调用自己，必须在某种意义上更趋近解

递归模板

1 写递归终止条件

2 处理递归逻辑

3 如果有需要，处理递归结果

    /**
     * 递归调用的最深层次，不一定是整数，但是需要自己判断
     */
    private static final int MAX_LEVEL = 100;

    /**
     * 递归模板，自己修改方法名称
     * @param level  当前递归所处的层级，方便知道自己的位置。
     * @param results 每一层递归对应的结果 , 也可以是Map，一方面用来保存每一层的结果，另外可以用于调试递归代码
     * @param params 每次进行递归处理的参数
     */
    public static void recursion(int level, Collection results, String... params) {
        // 1. 满足递归终止的条件
        if (level > MAX_LEVEL){
            return;
        }

        // 2. 如果不需要终止递归，进行递归真正要做的事情
        Object processedData = processData(level, params);
        results.add(processedData);

        // 3. 进行递归
        recursion(level+1,results,params);

        // 4. 是否对最后的数据做一些处理
        doSomethingIfNeed();

    }

案例

斐波那契数列

import java.util.HashMap;
import java.util.Map;

/**
 * @author : aihe aihe.ah@alibaba-inc.com
 * @date : 2020/2/17 8:28 上午
 * 使用场景：
 * 功能描述：
 * 斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
 *
 * F(0) = 0,   F(1) = 1
 * F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
 */
public class FabDemo {
    public static void main(String[] args) {
        HashMap result = new HashMap();
        int fab = fab(0, result, 5);
        System.out.println(fab);
        System.out.println(result);
    }

    /**
     * 斐波那契数递归求解
     * F(N) = F(N - 1) + F(N - 2)    1
     * F(N - 1) = F(N - 2) + F(N - 3)  2
     * ...
     * F(2) = F(1) + F(0)    ...  N-1
     * F(1) = 1   N
     * F(0) = 0   N + 1
     *
     * @param level
     * @param result
     * @param n
     */
    public static int fab(int level, Map result, int n) {
        // level = n
        if (n == 1) {
            return 1;
        }

        // level == n + 1
        if (n == 0) {
            return 0;
        }

        int fabN = fab(level + 1, result, n - 1) + fab(level + 2, result, n - 2);
        result.put(n,fabN);
        return fabN;
    }

}

二叉树的前序遍历

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [1,2,3]

public class TreeTraverseDemo {

    public List<Integer> preorderTraversal(TreeNode root) {
        List result =  new LinkedList<Integer>();
        doPreOrder(result,root);
        return result;
    }

    /**
     * 先序遍历(Pre-order)，按照根左右的顺序沿一定路径经过路径上所有的结点。在二叉树中，先根后左再右。巧记：根左右。
     * 1. 找终止条件，即当前节点为空，则终止继续遍历
     * 2. 处理逻辑： 将当前节点加入集合中
     * 3. 继续递归
     * @param list
     * @param root
     */
    public void doPreOrder(List<Integer> list,TreeNode root){
        if(root == null){
            return;
        }
        list.add(root.val);
        doPreOrder(list,root.left);
        doPreOrder(list,root.right);
    }


    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}

最后

这里主要就是想介绍下递归的解题流程，模板根据具体的场景稍作修改，思考每次处理是否采用相同的方法，编写时：

方法体：
- 首先，终止的条件是什么
- 具体做了什么事
- 是否要对结果进行处理
- 继续递归(调用方法体)