recursion - 递归的真实示例

Question

除了深度优先搜索（DFS）之外，递归方法是自然解决方案的实际问题是什么？

（我不考虑河内塔、斐波那契数或阶乘现实问题。在我看来，它们有点做作。）

score 114 · Accepted Answer

114

递归的真实示例

向日葵

于 2008-09-19T21:51:15.047 回答

score 65 · Accepted Answer

涉及文件系统中目录结构的任何事情怎么样。递归查找文件、删除文件、创建目录等。

这是一个 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());
            }
        }       
    }

}

score 62 · Accepted Answer

这里有很多数学例子，但你想要一个真实世界的例子，所以稍微思考一下，这可能是我能提供的最好的：

你会发现一个人感染了某种非致命性的传染性感染，并且很快就会自我修复（A 型），除了五分之一的人（我们将称之为 B 型）永久感染它并且没有表现出症状，只是充当传播者。

当 B 型感染大量 A 型时，这会造成相当烦人的破坏浪潮。

你的任务是追踪所有 B 型病毒并对其进行免疫以阻止疾病的主干。不幸的是，你不能对所有人进行全国性的治疗，因为 A 型的人对 B 型的治疗也有致命的过敏。

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

处理给定人员后，从队列前面选择人员并在需要时进行免疫接种。获取他们之前未访问过的所有联系人，然后测试他们是否被感染。

重复直到感染者的队列变为0，然后等待再次爆发。

（好吧，这有点迭代，但它是解决递归问题的迭代方式，在这种情况下，广度优先遍历人口基数试图发现问题的可能路径，此外，迭代解决方案通常更快更有效，并且我强迫性地在所有地方都删除递归，以至于它变得本能......该死！）

score 44 · Accepted Answer

44

快速排序、归并排序和大多数其他 N-log N 排序。

于 2008-09-19T21:37:35.267 回答

score 16 · Accepted Answer

马特迪拉德的例子很好。更一般地，树的任何行走通常都可以很容易地通过递归来处理。例如，编译解析树、遍历 XML 或 HTML 等。

score 16 · Accepted Answer

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

score 14 · Accepted Answer

只要可以通过将问题划分为子问题来解决问题，就可以使用递归，这些子问题可以使用相同的算法来解决它们。树和排序列表上的算法很自然。计算几何（和 3D 游戏）中的许多问题都可以使用二进制空间分区(BSP) 树、胖细分或其他将世界划分为子部分的方法递归地解决。

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

score 11 · Accepted Answer

肯定有很多编译器大量使用递归。计算机语言本身就是递归的（即，您可以将“if”语句嵌入到其他“if”语句中，等等）。

score 9 · Accepted Answer

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

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);
    }
}

score 8 · Accepted Answer

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

在字典中查找单词通常是通过类似于二分搜索的技术来执行的，该技术是递归的。

在组织中，老板经常向部门负责人下达命令，部门负责人又向经理下达命令，依此类推。

score 8 · Accepted Answer

来自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))))

这是应用的定义：

(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-> apply-> eval-sequence->eval

score 7 · Accepted Answer

7

递归用于诸如 BSP 树之类的游戏开发（和其他类似领域）中的碰撞检测。

于 2008-09-19T21:38:06.683 回答

score 7 · Accepted Answer

7

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

需求 A：在彻底理解需求 A 后实现此功能。

于 2008-09-19T22:14:03.697 回答

score 4 · Accepted Answer

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

score 4 · Accepted Answer

4

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

于 2008-09-19T21:51:11.457 回答

score 4 · Accepted Answer

在函数式编程语言中可以找到一些很好的递归示例。在函数式编程语言（Erlang、Haskell、ML / OCaml / F#等）中，任何列表处理都使用递归是很常见的。

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

当与模式匹配结合使用时，这种对列表的处理非常强大。假设我想总结一个数字列表：

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

这实质上是说“如果我们被一个空列表调用，则返回 0”（允许我们中断递归），否则返回 head 的值 + 使用剩余项调用的 Sum 的值（因此，我们的递归）。

例如，我可能有一个URL列表，我认为拆分每个 URL 链接到的所有 URL，然后我减少所有 URL 的链接总数以生成页面的“值”（谷歌的一种方法与PageRank一起使用，您可以在原始MapReduce论文中找到定义）。您也可以这样做以在文档中生成字数统计。还有很多很多其他的事情。

您可以将此功能模式扩展到任何类型的MapReduce代码，您可以在其中获取某些内容的列表，对其进行转换并返回其他内容（无论是另一个列表，还是列表中的某个 zip 命令）。

score 4 · Accepted Answer

递归应用于问题（情况），您可以将其分解（减少）为更小的部分，并且每个部分看起来都与原始问题相似。

包含与其自身相似的较小部分的事物的好例子是：

树形结构（一个分支就像一棵树）
列表（列表的一部分仍然是列表）
容器（俄罗斯娃娃）
序列（序列的一部分看起来像下一个）
对象组（子组仍然是一组对象）

递归是一种不断将问题分解成越来越小的部分的技术，直到其中一个变得小到可以小菜一碟。当然，在你分解它们之后，你必须以正确的顺序将结果“缝合”在一起，以形成原始问题的整体解决方案。

一些递归排序算法、tree-walking 算法、map/reduce 算法、分治法都是这种技术的例子。

在计算机编程中，大多数基于堆栈的调用返回类型语言已经具有内置的递归功能：即

将问题分解成更小的部分 ==> 在原始数据的较小子集上调用自身），
跟踪碎片是如何划分的 ==> 调用堆栈，
将结果缝合回去 ==> 基于堆栈的返回

score 4 · Accepted Answer

分层组织中的反馈循环。

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

每个高管都会收集他/她的直接下属，并告诉他们从直接下属那里收集反馈。

并在下线。

没有直接下属的人——树中的叶子节点——给出他们的反馈。

反馈返回树上，每个经理都添加他/她自己的反馈。

最终，所有的反馈都会反馈给最高老板。

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

score 3 · Accepted Answer

3

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

于 2008-09-19T21:39:32.360 回答

score 3 · Accepted Answer

通过递归解决的“现实世界”问题将是嵌套娃娃。你的函数是 OpenDoll()。

给定一堆它们，你会递归地打开娃娃，如果你愿意的话，调用 OpenDoll()，直到你到达最里面的娃娃。

score 2 · Accepted Answer

解析XML文件。
在多维空间中进行高效搜索。例如。2D 中的四叉树、3D 中的八叉树、kd 树等。
层次聚类。
想一想，遍历任何层次结构自然会导致递归。
C++ 中的模板元编程，没有循环，递归是唯一的方法。

score 2 · Accepted Answer

假设你正在为一个网站构建一个 CMS，你的页面是树形结构，比如根是主页。

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

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

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

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

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

score 2 · Accepted Answer

您有一个深度为 N 级的组织树。检查了几个节点，并且您希望仅扩展到已检查的那些节点。

这是我实际编码的东西。递归很好很容易。

score 2 · Accepted Answer

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

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

score 2 · Accepted Answer

2

金融/物理计算，例如复合平均值。

于 2008-09-19T22:14:47.423 回答

score 2 · Accepted Answer

我知道的最好的例子是quicksort，递归要简单得多。看一眼：

shop.oreilly.com/product/9780596510046.do

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

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

score 2 · Accepted Answer

2

解析Windows 窗体或 WebForms (.NET Windows Forms / ASP.NET ) 中的控件树。

于 2008-09-20T09:28:06.977 回答

score 1 · Accepted Answer

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

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

score 1 · Accepted Answer

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

score 1 · Accepted Answer

大多数情况下，递归对于处理递归数据结构是非常自然的。这基本上意味着列表结构和树结构。但是递归也是以某种方式动态/创建/树结构的一种很好的自然方式，通过分而治之，例如快速排序或二分搜索。

我认为你的问题在某种意义上有点误导。深度优先搜索与现实世界有何不同？深度优先搜索可以做很多事情。

例如，我想到的另一个例子是递归下降编译。在许多现实世界的编译器中使用它就足够了一个现实世界的问题。但你可以说它是 DFS，它基本上是对有效解析树的深度优先搜索。

score 1 · Accepted Answer

同上关于编译器的评论。抽象语法树节点自然适合递归。所有递归数据结构（链表、树、图等）也更容易使用递归处理。我确实认为，由于现实世界问题的类型，一旦我们离开学校，我们大多数人就不会经常使用递归，但最好意识到它是一种选择。

score 1 · Accepted Answer

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

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

score 1 · Accepted Answer

1

任何具有树或图数据结构的程序都可能有一些递归。

于 2008-09-19T22:39:37.847 回答

score 1 · Accepted Answer

1

编写一个函数，将像 12345.67 这样的数字转换为“12345 美元和 67 美分”。

于 2008-09-20T00:03:52.637 回答

score 1 · Accepted Answer

我曾经写过一个 XML 解析器，如果没有递归，它会更难写。

我想你总是可以使用堆栈+迭代，但有时递归是如此优雅。

score 1 · Accepted Answer

在平均情况 O(n) 中找到中位数。相当于在 n 个事物的列表中找到第 k 个最大的项目，其中 k=n/2：

int kthLargest(list, k, first, last) { j = partition(list, first, last) if (k == j) return list[j] else if (k

在这里，partition选择一个枢轴元素，并在一次遍历数据中重新排列列表，使小于枢轴的项目首先出现，然后是枢轴，然后是大于枢轴的项目。“kthLargest”算法与快速排序非常相似，但只在列表的一侧递归。

对我来说，这是最简单的递归算法，比迭代算法运行得更快。它平均使用 2*n 次比较，与 k 无关。这比运行 k 遍历数据、每次找到最小值并丢弃它的幼稚方法要好得多。

阿莱霍

score 1 · Accepted Answer

如果不是因为导致堆栈溢出的实际限制，那么使用迭代的所有事情都可以通过递归更自然地完成；-)

但是严重的是递归和迭代是非常可互换的，您可以使用递归重写所有算法以使用迭代，反之亦然。数学家喜欢递归，程序员喜欢迭代。这可能也是你看到你提到的所有这些人为例子的原因。我认为称为数学归纳的数学证明方法与数学家为什么喜欢递归有关。 http://en.wikipedia.org/wiki/Mathematical_induction

score 0 · Accepted Answer

我刚刚编写了一个递归函数来确定一个类是否需要使用 DataContractSerializer 进行序列化。最大的问题来自模板/泛型，其中一个类可能包含需要数据合同序列化的其他类型......所以它会遍历每种类型，如果它不是 datacontractserializable 检查它的类型。

score 0 · Accepted Answer

我们使用它们来进行 SQL 寻路。

我还要说调试很费劲，可怜的程序员很容易搞砸。

score 0 · Accepted Answer

我认为这真的取决于语言。在某些语言中，例如Lisp，递归通常是对问题的自然反应（通常在这种情况下，编译器会针对递归进行优化）。

Lisp 中的常见模式是对列表的第一个元素执行操作，然后在列表的其余部分上调用函数以累积一个值或一个新列表，这是一种非常优雅和最自然的方式来做很多事情那种语言的东西。在Java中，没有那么多。

score 0 · Accepted Answer

我在 C# 中编写了一个树来处理对具有默认情况的 6 段键的表的查找（如果键 [0] 不存在，则使用默认情况并继续）。查找是递归完成的。我尝试了字典（等）的字典，它很快就变得太复杂了。

我还在 C# 中编写了一个公式评估器，它评估存储在树中的方程以使评估顺序正确。当然，这很可能是为问题选择了不正确的语言，但这是一个有趣的练习。

我没有看到很多关于人们所做的事情的例子，而是他们使用过的库。希望这能给你一些思考。

score 0 · Accepted Answer

0

GIS 或制图的几何计算，例如寻找圆的边缘。

于 2008-09-19T22:15:05.707 回答

score 0 · Accepted Answer

0

求平方根的方法是递归的。用于计算现实世界中的距离。

于 2008-09-19T22:15:45.690 回答

score 0 · Accepted Answer

寻找素数的方法是递归的。用于生成散列密钥，适用于使用大数因子的各种加密方案。

score 0 · Accepted Answer

你有一栋楼。该建筑有20间客房。从法律上讲，每个房间只能容纳一定数量的人。您的工作是自动将人员分配到一个房间。如果我的房间满了，你需要找到一个可用的房间。鉴于只有某些房间可以容纳某些人，您还需要注意哪个房间。

例如：

房间 1、2、3 可以互相滚动。这个房间是为不能自己走路的孩子准备的，所以你希望他们远离其他一切，以避免分心和其他疾病（这对老年人来说不是一件事情，但对于一个 6 个月的孩子来说，这可能会变得非常糟糕。应该三个人都满了，这个人必须被拒绝进入。

房间 4、5、6 可以互相滚动。这个房间是为对花生过敏的人准备的，因此他们不能进入其他房间（可能有花生的东西）。如果这三个人都吃饱了，提供一个警告，询问他们的过敏水平，并且他们可以被授予访问权限。

在任何给定时间，房间都可能发生变化。所以你可以允许房间 7-14 是没有花生的房间。你不知道要检查多少个房间。

或者，也许您想根据年龄分开。年级、性别等。这些只是我遇到的几个例子。

score 0 · Accepted Answer

检查创建的图像是否可以在尺寸受限的框中工作。

function check_size($font_size, $font, $text, $width, $height) {
        if (!is_string($text)) {
            throw new Exception('Invalid type for $text');
        }   
        $box = imagettfbbox($font_size, 0, $font, $text);
        $box['width'] = abs($box[2] - $box[0]);
        if ($box[0] < -1) {
            $box['width'] = abs($box[2]) + abs($box[0]) - 1;
        }   
        $box['height'] = abs($box[7]) - abs($box[1]);
        if ($box[3] > 0) {
            $box['height'] = abs($box[7] - abs($box[1])) - 1;
        }   
        return ($box['height'] < $height && $box['width'] < $width) ? array($font_size, $box['width'], $height) : $this->check_size($font_size - 1, $font, $text, $width, $height);
    }

score 0 · Accepted Answer

一种使用亚音速从数据库表生成树状结构菜单的方法。

public MenuElement(BHSSiteMap node, string role)
    {
        if (CheckRole(node, role))
        {
            ParentNode = node;

            // get site map collection order by sequence
            BHSSiteMapCollection children = new BHSSiteMapCollection();

            Query q = BHSSiteMap.CreateQuery()
                    .WHERE(BHSSiteMap.Columns.Parent, Comparison.Equals, ParentNode.Id)
                    .ORDER_BY(BHSSiteMap.Columns.Sequence, "ASC");

            children.LoadAndCloseReader(q.ExecuteReader());

            if (children.Count > 0)
            {
                ChildNodes = new List<MenuElement>();

                foreach (BHSSiteMap child in children)
                {
                    MenuElement childME = new MenuElement(child, role);
                    ChildNodes.Add(childME);
                }
            }
        }
    }

score 0 · Accepted Answer

我有的最后一个真实世界的例子是一个非常无聊的例子，但它展示了递归有时是如何“恰到好处”的。

我使用的是责任链模式，因此 Handler 对象要么自己处理请求，要么将其委托给链。记录链的构造很有用：

public String getChainString() {
    cs = this.getClass().toString();
    if(this.delegate != null) {
        cs += "->" + delegate.getChainString();
    }
    return cs;
}

您可能会争辩说这不是最纯粹的递归，因为尽管该方法调用“自身”，但每次调用它时它都在不同的实例中。

score 0 · Accepted Answer

递归是一种非常基本的编程技术，它适用于许多问题，列出它们就像列出所有可以通过使用某种加法来解决的问题。只是通过我的 Project Euler 的 Lisp 解决方案，我发现：一个交叉总计函数、一个数字匹配函数、几个用于搜索空格的函数、一个最小的文本解析器、一个将数字拆分为其十进制数字列表的函数、一个函数构造一个图，以及一个遍历输入文件的函数。

问题是当今许多（如果不是大多数）主流编程语言都没有尾调用优化，因此深度递归对它们来说是不可行的。这种不足意味着大多数程序员被迫放弃这种自然的思维方式，转而依赖其他可能不太优雅的循环结构。

score 0 · Accepted Answer

如果您有两个不同但相似的序列，并且想要匹配每个序列的组件，以便首先优先考虑大的连续块，然后是相同的序列顺序，那么您可以递归分析这些序列以形成一棵树，然后递归处理该树以展平它。

参考： 递归和记忆示例代码

score 0 · Accepted Answer

0

插头： http: //picogen.deviantart.com/gallery/

在此处输入图像描述

于 2011-09-13T20:03:00.640 回答

score 0 · Accepted Answer

大学储蓄计划：让 A(n) = n 个月后为大学节省的金额 A(0) = $500 每个月，$50 存入一个年利率为 5% 的账户。

然后A(n) = A(n-1) + 50 + 0.05*(1/12)* A(N-1)

score 0 · Accepted Answer

由于您似乎不喜欢计算机科学或数学示例，因此这里有一个不同的示例：连线谜题。

许多金属丝谜题涉及通过在金属丝环内外加工来去除长长的闭合回路。这些谜题是递归的。其中之一被称为“箭头动力学”。如果你用谷歌搜索“箭头动力学线谜”，我想你可以找到它

这些谜题很像河内的塔。

score -3 · Accepted Answer

间接递归的一个真实例子是问你的父母你是否可以在圣诞节玩那个电子游戏。爸爸：“问妈妈。”……妈妈：“问爸爸。” [简而言之，“不，但我们不想告诉你，以免你发脾气。”]

score -3 · Accepted Answer

河内塔

这是您可以与之互动的一个：http: //www.mazeworks.com/hanoi/

使用递归关系，该解决方案所需的确切移动次数可以计算为：2h - 1。这个结果是通过注意到步骤 1 和 3 采取 Th - 1 移动，而步骤 2 采取 1 移动，得到 Th = 2Th − 1 + 1。见：http ://en.wikipedia.org/wiki/Towers_of_hanoi#Recursive_solution

recursion - 递归的真实示例

55 回答 55

递归的真实示例

来自SICP的著名评估/应用周期

Related

Reference