递归与分治深入认识

发布时间：2021-11-12 11:50:59 所属栏目：教程来源：互联网

导读：函数调用自己，是递归的用法，是对递归很浅的一种认识。斐波那契数列应该就是我们遇到的最基础的递归了，那时候的我，还只知道怎么用递归。关于递归，维基百科上这样说：递归：在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象

“函数调用自己”，是递归的用法，是对递归很浅的一种认识。斐波那契数列应该就是我们遇到的最基础的递归了，那时候的我，还只知道怎么用递归。

关于递归，维基百科上这样说：

递归：在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。

拆解它的关键点来说：

简单的基本情况：也就是递归的终结条件，在上面的例子中，基本情况就是 fetchCount 等于 1，在斐波纳契数列中，基本情况就是第 1、2 个元素都是 1。
其他所有情况都能还原为其基本情况：即递归中所有情况都是相似的，且要能够把其他情况还原成基本情况。

在上面全排列的例子中，所有情况都相似在从 M 个元素中取 N 个元素，放入到结果集合中，且最后都简化到了从 X 个元素中取一个的情况。在斐波那契数列中，所有的情况都相似在，N 等于第 N-1 个元素加上第 N-2 个元素，且都能从后到前简化到第 1、2 个元素求和。

还原：当然不能忘记这个重要步骤。
递归和分治
回想一下分治的思想，是不是和递归异曲同工？

它们都是倾向于将问题化简，直到化简到某一个终结条件，再层层向上追溯。

其实递归和分治并无不同，递归使用的就是分治的思想，它是分治思想的一种具体实现。

递归实现的可变嵌套层数
public class Exhaustion {
    private static List<String> m = Arrays.asList("a", "b", "c", "d", "e");

    public static void main(String[] args) {
        int n = 5;

        Set<Set<String>> combinationAll = new HashSet<>();
        for (int c = 1; c <= n; c++) {
            Set<Set<String>> duplicated = exhaustion(new HashSet<>(), c);
            for (Set<String> set : duplicated) {
                if (set.size() == c) {
                    combinationAll.add(set);
                }
            }
        }

        System.out.println(combinationAll);
    }

    private static Set<Set<String>> exhaustion(Set<String> tempSet, int count) {
        Set<Set<String>> result = new HashSet<>();

        if (count == 1) {
            Set<Set<String>> finalCollection = new HashSet<>();
            for (String ele : m) {
                Set<String> tempCollection = new HashSet<>(tempSet);
                tempCollection.add(ele);
                finalCollection.add(tempCollection);
            }

            return finalCollection;
        }

        count--;
        for (int i = 1; i < m.size(); i++) {
            Set<String> tempCollection = new HashSet<>(tempSet);
            tempCollection.add(m.get(i));
            result.addAll(exhaustion(tempCollection, count));
        }

        return result;
    }
}

（编辑：PHP编程网 - 黄冈站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

采用gpt分区无法安装系	跟你说进程管理器快捷
电脑装机必备清单	小编教你联想笔记本进