手机版
你好,游客 登录 注册
背景:
阅读新闻

递归与分治深入理解

[日期:2019-04-01] 来源:zhenbianshu.github.io  作者:zhenbianshu [字体: ]

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

关于递归,维基百科上这样说:

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

拆解它的关键点来说:

  • 简单的基本情况: 也就是递归的终结条件,在上面的例子中,基本情况就是 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;
    }
}

Linux公社的RSS地址https://www.linuxidc.com/rssFeed.aspx

本文永久更新链接地址https://www.linuxidc.com/Linux/2019-04/157878.htm

linux
相关资讯       递归  分治 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款