迭代转递归

我们先看个例子

/**
 * 使用树来进行迭代
 * 当然在没有分叉的情况下树迭代与简单递归是一样的
 * 对一个数组循环求和，以下使用迭代与递归两种方式来实现
 */
public class TreeIteration {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8,9};
        TreeIteration binaryTree = new TreeIteration();
        System.out.println(binaryTree.getSum(arr));
        System.out.println(binaryTree.getSumByRecursion(arr));
    }

    public int getSum(int[] arr) {
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
        }
        return sum;
    }

    public int getSumByRecursion(int[] arr) {
        return dfs(arr, 0);
    }

    int dfs(int[] arr, int i) {
        // 递归出口，相当于迭代的for循环里面的结束条件
        if (i == arr.length - 1) {
            return arr[i];
        }
        // 递归调用dfs函数，在传入数组下标参数时+1，相当于迭代的i++
        return arr[i] + dfs(arr, i+1);
    }
}

尾递归

尾递归和一般的递归不同在对内存的占用，普通递归创建stack累积而后计算收缩，尾递归只会占用恒量的内存（和迭代一样）。尾递归是把变化的参数传递给递归函数的变量了。

怎么写尾递归？形式上只要最后一个return语句是单纯函数就可以。如：return dfs(arr, i+1);

简单来讲，尾递归是指在一个方法内部，递归调用后直接return，没有任何多余的指令了。

int dfs(int[] arr, int i) {
    // 递归出口，相当于迭代的for循环里面的结束条件
    if (i == arr.length - 1) {
        return arr[i];
    }
    // 递归调用dfs函数，在传入数组下标参数时+1，相当于迭代的i++
    return arr[i] + dfs(arr, i+1);
}

请问这个是尾递归么？答案是否定的。可能有的人会说，明明最后一个步骤就是调用dfs，为啥不是尾递归？实际上，你看到的最后一个步骤不代表从指令层面来讲的最后一步。这个方法的return先拿到dfs(n-1)的值，然后再将n与其相加，所以求dfs(n-1)并不是最后一步，因为最后还有一个add操作。

采用尾递归优化一下：

public int getSumByTailRecursion(int[] arr) {
    return dfs1(arr, 0, 0);
}

int dfs1(int[] arr, int i, int sum) {
    if (i == arr.length - 1) {
        return arr[i] + sum;
    }
    return dfs1(arr, i+1, arr[i] + sum);
}

尾递归由于将外层方法的结果传递给了内层方法，那外层方法实际上没有任何利用价值了，直接从栈里踢出去就行了，所以可以保证同时只有一个栈帧在栈里存活，节省了大量栈空间。

递归的实现

递归和循环是等价的

如果定义一个概念需要用到这个概念本身，我们称它的定义是递归的（Recursive）

递归和循环是等价的，用循环能做的事用递归都能做，反之亦然。

尾调用 (tail call) 和尾递归 (tail recursion)

• 非尾递归算法，需要O(n)的调用栈空间
• 尾递归是尾调用的特殊情形，尾调用并不要求 callee 和 caller 是同一个函数。
• 尾递归太特殊了，太容易优化了，所以在源码层面就能做递归到迭代的变换。

任何的递归，都可以转换成尾调用，然后优化。

• 如果算法本身就是尾递归的，那么，可以直接改写成迭代，这是尾调用优化的一种特例。
• 如果算法本身是非尾递归的，那么，CPS 变换可以将算法改写成尾调用形式，从而可以进行尾调用优化。改写过后的空间复杂度仍然是 O(n)，只不过是从 O(n) 的栈变成了 O(n) 的 continuation chain，这个改变对支持尾调用优化的简单解释器是有意义的。

剪枝

从一个集合中选择符合条件的真子集的递归二叉树DFS剪枝模板

先看题目：

18. 四数之和 给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：答案中不可以包含重复的四元组。

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
通过次数127,257提交次数325,331
*
链接：https://leetcode-cn.com/problems/4sum/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

这道题不考虑时间复杂度的迭代解法

public List<List<Integer>> fourSum1(int[] nums, int target) {
    List<Integer> oneSolution = null;
    List<List<Integer>> output = new ArrayList<List<Integer>>();

    Arrays.sort(nums);

    for (int i = 0; i < nums.length - 3; i++) {
        for (int j = i + 1; j < nums.length - 2; j++) {
            for (int m = j + 1; m < nums.length - 1; m++) {
                for (int n = m + 1; n < nums.length; n++) {
                    if (target == nums[i] + nums[j] + nums[m] + nums[n]) {
                        oneSolution = new ArrayList<Integer>();
                        oneSolution.add(nums[i]);
                        oneSolution.add(nums[j]);
                        oneSolution.add(nums[m]);
                        oneSolution.add(nums[n]);
                        output.add(oneSolution);
                    }
                }
            }
        }
    }

    return output;
}

public class FourSum {
    public static void main(String[] args) {
        int[] nums = {1, 0, -1, 0, -2, 2};
        int target = 0;
        FourSum1 fourSum = new FourSum1();
        List<List<Integer>> result = fourSum.fourSum(nums, target);
        for (List<Integer> list : result) {
            System.out.println(list);
        }
    }

    public List<List<Integer>> fourSum(int[] nums, int target) {
        ArrayList<Integer> notSelected = new ArrayList<Integer>();
        List<Integer> oneSolution = new ArrayList<Integer>();
        List<List<Integer>> output = new ArrayList<List<Integer>>();

        Arrays.sort(nums);

        Search(0, target, oneSolution, notSelected, nums, output);

        return output;
    }

    public static void Search(int i, int target, List<Integer> oneSolution, ArrayList<Integer> notSelected, int[] nums, List<List<Integer>> output) {
        // 递归出口，当前选择的子数组达到4个且符合等于target的要求
        if ((target == 0) && (oneSolution.size() == 4)) {
            List<Integer> temp = new ArrayList<Integer>(oneSolution);
            output.add(temp);
            return;
        }
        // 递归出口，i超过数组长度或者一个解选择的数多于4个
        if ((i > nums.length - 1) || (oneSolution.size() > 4)) {
            return;
        }
        // 若当前数在不选的列表里跳过当前数判断下一个
        if (Inside(notSelected, nums[i])) {
            Search(i + 1, target, oneSolution, notSelected, nums, output);
            return;
        }
        // ========剪枝========
        // 剪枝条件一：若target > 当前数+剩余选择个数*剩下数组里最大的那个数 则表示对于已经选择的子数组而言当前选择的数太小需要向下找一个更大的数
        if ((target > nums[i] + (3 - oneSolution.size()) * nums[nums.length - 1])) {
            Search(i + 1, target, oneSolution, notSelected, nums, output);
            return;
        }
        // 剪枝条件二：若target < 剩余选择个数*当前数 则表示对于已经选择的子数组而言当前选择的数太大，且接下来选择的数只会更大，放弃当前选择的子数组
        if (target < (4 - oneSolution.size()) * nums[i]) {
            return;
        }
        // ====================
        // 假设选择当前数
        oneSolution.add(nums[i]);
        Search(i + 1, target - nums[i], oneSolution, notSelected, nums, output);
        oneSolution.remove(oneSolution.size() - 1);
        // 假设不选择当前数
        notSelected.add(nums[i]);
        Search(i + 1, target, oneSolution, notSelected, nums, output);
        notSelected.remove(notSelected.size() - 1);
    }

    public static boolean Inside(ArrayList<Integer> notSelected, int num) {
        for (int i : notSelected) {
            if (i == num) {
                return true;
            }
        }
        return false;
    }
}

根据上述代码可以总结出模板，这里的元素类型用int/Integer为例：

// nums为给定条件集合, target为符合要求的子集
public List<List<Integer>> fourSum(int[] nums, int target) {
    ArrayList<Integer> notSelected = new ArrayList<Integer>();
    List<Integer> oneSolution = new ArrayList<Integer>();
    List<List<Integer>> output = new ArrayList<List<Integer>>();

    Arrays.sort(nums);

    Search(0, target, oneSolution, notSelected, nums, output);

    return output;
}

/**
 * DFS搜索
 * @param i 迭代用的下标
 * @param target 判断子集符合要求的条件
 * @param oneSolution 其中一个子集
 * @param notSelected 不选择的元素
 * @param nums 条件给出的父集合
 * @param output 符合要求的子集组成的列表
 */
public static void Search(int i, int target, List<Integer> oneSolution, ArrayList<Integer> notSelected, int[] nums, List<List<Integer>> output) {
    // 递归出口，
    if (/*判断当前子集符合条件的代码*/) {
        // 若符合则把当前子集加入答案列表
        List<Integer> temp = new ArrayList<Integer>(oneSolution);
        output.add(temp);
        return;
    }
    // 递归出口，i超过数组长度
    if ((i > nums.length - 1)) {
        return;
    }
    // 若当前判断的元素在不选的列表里跳过当前元素判断下一个
    if (Inside(notSelected, nums[i])) {
        Search(i + 1, target, oneSolution, notSelected, nums, output);
        return;
    }
    // ========剪枝========
    // 剪枝(剪掉当前元素的枝)：当前元素加入就会导致当前判断的子集不符合要求则跳过当前元素继续判断
    if (/**/) {
        Search(i + 1, target, oneSolution, notSelected, nums, output);
        return;
    }
    // 剪枝(剪掉接下来判断的所有元素的枝，即剪掉当前枝)：若当前元素和以后的元素全部会导致当前子集不符合要求
    if (/**/) {
        return;
    }
    // ====================
    // 假设选择当前元素
    oneSolution.add(nums[i]);
    Search(i + 1, target - nums[i], oneSolution, notSelected, nums, output);
    oneSolution.remove(oneSolution.size() - 1);
    // 假设不选择当前元素
    notSelected.add(nums[i]);
    Search(i + 1, target, oneSolution, notSelected, nums, output);
    notSelected.remove(notSelected.size() - 1);
}
// 用来判断当前元素是否在不选择的列表里面
public static boolean Inside(ArrayList<Integer> notSelected, int num) {
    for (int i : notSelected) {
        if (i == num) {
            return true;
        }
    }
    return false;
}