真实世界的例子递归[封闭]

Question

是什么 真实世界 问题在哪里递归的方法是自然的解决方案一深度的第一个搜索(外勤部)?

(我不认为 塔河内, 斐波纳契数, 或因真实世界的问题。他们有点做作，在我的脑海里。)

Answer 1

这里有很多蹩脚的例子，但是你想要一个真实世界的例子，所以有一点想法，这可能是我能提供的最好的：

你发现一个人感染了特定的感染，这是非致命的，并迅速自我修复（A型），除了五分之一的人（我们称之为B型），他们会永久感染它并且没有任何症状，仅仅是一个吊具。

当B型感染多种A型时，这会产生非常恼人的破坏波。

你的任务是追踪所有类型的Bs并免疫它们以阻止疾病的骨干。不幸的是，你不能在全国范围内治疗所有人，因为那些类型的人对于治疗B型的治疗方法也是致命的过敏。

你这样做的方式是社交发现，给予感染者（A型），在上周选择所有联系人，在堆上标记每个联系人。当您测试某人受到感染时，请将其添加到“跟进”中。队列。当某人是B类时，将其添加到“跟进”中。在头部（因为你想要快速停止）。

处理完一个人后，从队列前面选择一个人，并在必要时进行免疫接种。获取以前未访问的所有联系人，然后测试他们是否被感染。

重复直到被感染者的队列变为0，然后等待另一次爆发..

（好吧，这有点迭代，但它是一种解决递归问题的迭代方法，在这种情况下，广泛首次遍历人口基础试图发现可能的问题路径，此外，迭代解决方案通常更快而且更加有效，我强迫性地去除各处的递归，这本身就变得本能了...... ....该死的！）

Answer 2

递归的真实例子

Answer 3

如何处理文件系统中的目录结构。递归查找文件，删除文件，创建目录等

这是一个Java实现，以递归方式打印出目录及其子目录的内容。

import java.io.File;

public class DirectoryContentAnalyserOne implements DirectoryContentAnalyser {

    private static StringBuilder indentation = new StringBuilder();

    public static void main (String args [] ){
        // Here you pass the path to the directory to be scanned
        getDirectoryContent("C:\\DirOne\\DirTwo\\AndSoOn");
    }

    private static void getDirectoryContent(String filePath) {

        File currentDirOrFile = new File(filePath);

        if ( !currentDirOrFile.exists() ){
            return;
        }
        else if ( currentDirOrFile.isFile() ){
            System.out.println(indentation + currentDirOrFile.getName());
            return;
        }
        else{
            System.out.println("\n" + indentation + "|_" +currentDirOrFile.getName());
            indentation.append("   ");

            for ( String currentFileOrDirName : currentDirOrFile.list()){
                getPrivateDirectoryContent(currentDirOrFile + "\\" + currentFileOrDirName);
            }

            if (indentation.length() - 3 > 3 ){
                indentation.delete(indentation.length() - 3, indentation.length());
            }
        }       
    }

}

Answer 4

Quicksort ，合并排序，以及大多数其他N-log N排序。

Answer 5

Matt Dillard的榜样很好。更一般地，树的任何行走通常可以非常容易地通过递归来处理。例如，编译解析树，遍历XML或HTML等

Answer 6

递归通常用于回溯算法的实现中。对于“真实世界”应用这个，数独求解器怎么样？

Answer 7

只要通过将问题分成子问题就可以解决问题，递归是合适的，可以使用相同的算法来解决问题。树和排序列表上的算法是很自然的。计算几何（和3D游戏）中的许多问题可以使用二进制空间分区（BSP）递归解决树木，脂肪细分，或将世界划分为子部分的其他方式。

当您尝试保证算法的正确性时，递归也是合适的。给定一个接受不可变输入的函数并返回一个结果，该结果是对输入的递归和非递归调用的组合，通常很容易使用数学归纳来证明函数是正确的（或不正确）。使用迭代函数或可能变异的输入来执行此操作通常是难以处理的。在处理财务计算和其他正确性非常重要的应用程序时，这非常有用。

Answer 8

当然很多编译器都会大量使用递归。计算机语言本身具有递归性（即，您可以在其他'if'语句中嵌入'if'语句等。）

Answer 9

禁用/设置容器控件中所有子控件的只读。我需要这样做，因为一些儿童控件本身就是容器。

public static void SetReadOnly(Control ctrl, bool readOnly)
{
    //set the control read only
    SetControlReadOnly(ctrl, readOnly);

    if (ctrl.Controls != null && ctrl.Controls.Count > 0)
    {
        //recursively loop through all child controls
        foreach (Control c in ctrl.Controls)
            SetReadOnly(c, readOnly);
    }
}

Answer 10

来自 SICP

_{（来源： mit.edu ）}

以下是eval的定义：

(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
        ((variable? exp) (lookup-variable-value exp env))
        ((quoted? exp) (text-of-quotation exp))
        ((assignment? exp) (eval-assignment exp env))
        ((definition? exp) (eval-definition exp env))
        ((if? exp) (eval-if exp env))
        ((lambda? exp)
         (make-procedure (lambda-parameters exp)
                         (lambda-body exp)
                         env))
        ((begin? exp) 
         (eval-sequence (begin-actions exp) env))
        ((cond? exp) (eval (cond->if exp) env))
        ((application? exp)
         (apply (eval (operator exp) env)
                (list-of-values (operands exp) env)))
        (else
         (error "Unknown expression type - EVAL" exp))))

以下是apply的定义：

(define (apply procedure arguments)
  (cond ((primitive-procedure? procedure)
         (apply-primitive-procedure procedure arguments))
        ((compound-procedure? procedure)
         (eval-sequence
           (procedure-body procedure)
           (extend-environment
             (procedure-parameters procedure)
             arguments
             (procedure-environment procedure))))
        (else
         (error
          "Unknown procedure type - APPLY" procedure))))

以下是eval-sequence的定义：

(define (eval-sequence exps env)
  (cond ((last-exp? exps) (eval (first-exp exps) env))
        (else (eval (first-exp exps) env)
              (eval-sequence (rest-exps exps) env))))

eval - ＆gt; apply - ＆gt; eval-sequence - ＆gt; <代码>评估

Answer 11

在BSP树之类的东西中使用递归来进行游戏开发（以及其他类似区域）中的碰撞检测。

Answer 12

人们经常使用递归方法对文档堆栈进行排序。例如，假设您正在对包含名称的100个文档进行排序。首先将文件放入第一个字母的堆中，然后对每个堆进行排序。

在字典中查找单词通常是通过类似二进制搜索的技术执行的，这是递归的。

在组织中，老板经常向部门主管发出命令，而部门负责人又向管理人员发出命令，等等。

Answer 13

解析器和编译器可以用递归下降方法编写。这不是最好的方法，因为像lex / yacc这样的工具可以生成更快，更高效的解析器，但在概念上简单易用，所以它们仍然很常见。

Answer 14

我最近得到的真实世界要求：

要求A：在彻底理解要求A后实施此功能。

Answer 15

递归施加的问题(的情况)那里你可以打破它(减少)成更小的部分，并且每个部分(s)看起来类似原来的问题。

好的例子里的东西包含较小的部分相似本身是：

• 树形结构(分支是像一棵树)
• 列出(列表的一部分仍然是一个列表)
• 容器(俄罗斯的娃娃)
• 序列(第一部分的一个顺序看起来像下)
• 对象组(一个小组是一个仍然是一组的对象)

递归的技术，以保持破坏问题的解为较小的和较小的碎片，直到这些碎片得足够小到可以一块蛋糕。然后你打了，然后，必须"针"的结果一起回来的权利，以便形成一个总的解决原来的问题。

一些递归的排序的算法，树-走的算法、地图/减少的算法、分而治之的是所有这方面的例子技术。

在计算机编程，大多数基于栈的话回报类型的语言已经有能力建立在递归:即

• 打破的问题下的成更小的碎片==>话本身在一个较小的子集原始数据)，
• 跟踪关于如何件分==>呼栈，
• 针的结果返回==>堆基于返回

Answer 16

我有一个系统在几个地方使用纯尾递归来模拟一个州机。

Answer 17

函数式编程语言中提供了一些很好的递归示例。在函数式编程语言中（ Erlang ， Haskell ， ML / OCaml / F＃等），让任何列表处理都使用递归是很常见的。

在处理典型命令式OOP风格语言中的列表时，将列表实现为链接列表（[item1 - ＆gt; item2 - ＆gt; item3 - ＆gt; item4]）非常常见。但是，在某些函数式编程语言中，您会发现列表本身是递归实现的，其中“head”是“head”。列表中的第一项指向列表中的第一项，并且“尾部”指的是“尾部”。指向包含其余项目的列表（[item1 - ＆gt; [item2 - ＆gt; [item3 - ＆gt; [item4 - ＆gt; []]]]]）。我认为这很有创意。

这种列表处理与模式匹配相结合，非常强大。假设我要总结一个数字列表：

let rec Sum numbers =
    match numbers with
    | [] -> 0
    | head::tail -> head + Sum tail

这基本上说“如果我们用空列表调用，则返回0”。 （允许我们打破递归），否则返回head的值+使用剩余项调用的Sum的值（因此，我们的递归）。

例如，我可能会有一个网址的列表，我想打破所有每个URL链接到的URL，然后我减少与所有URL的链接总数，以生成“值”。对于一个页面（Google采用的方法是 PageRank 并且您可以在原始文件中找到 MapReduce 论文）。您也可以这样做以在文档中生成单词计数。还有很多很多其他的东西。

您可以将此功能模式扩展到任何类型的 MapReduce 代码，您可以在一些东西的列表，转换它，并返回其他东西（无论是另一个列表，还是列表上的一些zip命令）。

Answer 18

XML，或遍历任何树。虽然，说实话，我几乎从不在工作中使用递归。

Answer 19

分层组织中的反馈循环。

高层老板告诉高层管理人员收集公司每个人的反馈意见。

每位高管都会收集他/她的直接下属，并告诉他们收集直接下属的反馈意见。

然后就行了。

没有直接报告的人 - 树中的叶节点 - 提供反馈。

反馈回到树上，每位经理都加入他/她自己的反馈。

最终，所有反馈都会让它回到顶级老板。

这是一种自然的解决方案，因为递归方法允许在每个级别进行过滤 - 重复项的整理和删除令人反感的反馈。顶级老板可以发送全球电子邮件，并让每位员工直接向他/她报告反馈，但有“你无法处理真相”。并且“你被解雇了”问题，所以这里的递归效果最好。

Answer 20

假设您正在为网站构建CMS，其中您的网页采用树形结构，并且根目录是主页。

假设您的{user | client | customer | boss}请求您在每个页面上放置一个痕迹痕迹，以显示您在树中的位置。

对于任何给定页面n，您可能希望以递归方式向上走到n的父级及其父级，依此类推，以构建返回到页面树根的节点列表。

当然，在该示例中，您每次都会多次访问数据库，因此您可能希望使用一些SQL别名来查找页表作为a，并将页表再次作为b，并加入a .id与b.parent，所以你让数据库做递归连接。已经有一段时间了，所以我的语法可能没用。

然后，您可能只想计算一次并将其与页面记录一起存储，只有在移动页面时才更新它。这可能会更有效率。

无论如何，这是我的$ .02

Answer 21

您有一个N级深度的组织树。检查了几个节点，并且您只想扩展到已经检查过的那些节点。

这是我实际编码的内容。 它很好，很容易递归。

Answer 22

在我的工作中，我们有一个具有通用数据结构的系统，可以将其描述为树。这意味着递归是处理数据的一种非常有效的技术。

在没有递归的情况下解决它需要大量不必要的代码。递归的问题在于跟踪发生的事情并不容易。在执行流程时，您必须集中注意力。但是当它工作时，代码优雅而有效。

Answer 23

财务/物理的计算，例如复合平均值。

Answer 24

• 分析 XML 文件。
• 有效的搜索，在多维空间。E.g。四树木在2D，oct-树木在3D，kd树，等等。
• 层次的聚类。
• 我想起来了，穿越任何等级结构自然地适合于递归。
• 模板元编程在C++，那里有没有循环和递归的唯一方式。

Answer 25

在 Windows窗体或WebForms（.NET Windows窗体/ <）中解析控件树a href =“http://en.wikipedia.org/wiki/ASP.NET”rel =“nofollow noreferrer”> ASP.NET ）。

Answer 26

我所知道的最好的例子是 quicksort ，它在递归方面要简单得多。看看：

shop.oreilly.com/product/9780596510046.do

www.amazon.com/Beautiful-Code-Leading-Programmers-Practice/dp / 0596510047

（点击第3章下的第一个副标题：“我写过的最漂亮的代码”）。

Answer 27

电话和有线电视公司维护其布线拓扑模型，实际上是一个大型网络或图形。当您想要查找所有父元素或所有子元素时，递归是遍历此模型的一种方法。

由于从处理和内存的角度来看递归是昂贵的，所以此步骤通常仅在更改拓扑并且结果以修改的预先排序的列表格式存储时执行。

Answer 28

归纳推理是概念形成的过程，本质上是递归的。在现实世界中，你的大脑会一直这样做。

Answer 29

同样关于编译器的评论。抽象语法树节点自然适合递归。所有递归数据结构（链表，树，图等）也可以通过递归更轻松地处理。我确实认为，由于现实问题的类型，我们大多数人一旦离开学校就不会使用递归，但最好将其作为一种选择。

Answer 30

自然数的乘法是递归的真实例子：

To multiply x by y
  if x is 0
    the answer is 0
  if x is 1
    the answer is y
  otherwise
    multiply x - 1 by y, and add x