除了深度优先搜索(DFS)以外，递归方法是自然解决方案的现实问题是什么？

(我不考虑河内之塔，斐波那契数或者现实世界中的阶乘问题。在我看来，这些问题有些人为设置。)

解决方案

文件系统中涉及目录结构的所有内容如何。递归查找文件，删除文件，创建目录等。

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

}

快速排序，合并排序和大多数其他N对数N排序。

递归用于BSP树之类的事物，用于游戏开发(以及其他类似区域)中的冲突检测。

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

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

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

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

当然，那里的许多编译器都大量使用递归。计算机语言本身就具有递归性(例如，我们可以将" if"语句嵌入其他" if"语句中，等等)。

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

给定它们的堆栈，我们将递归打开玩偶，如果可以的话，调用OpenDoll()，直到到达最里面的玩偶为止。

递归经常用于回溯算法的实现中。对于此的"实际"应用程序，数独求解器如何？

归纳推理是概念形成的过程，本质上是递归的。大脑在现实世界中始终无休止地工作。

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

假设我们正在为网站构建CMS，其中页面是树状结构，并且说根是主页。

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

对于任何给定的页面n，我们可能需要递归到n的父级，及其父级，依此类推，以递归方式建立备份到页面树根的节点列表。

当然，在该示例中，我们在每个页面上多次击中数据库，因此我们可能需要使用一些SQL别名，在其中将page-table查找为a，然后将page-table查找为b，然后将a.id与b.parent，以便我们使数据库执行递归联接。已经有一段时间了，所以我的语法可能没有帮助。

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

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

我们有一个N层深的组织树。已检查了几个节点，并且我们想扩展到仅那些已被检查的节点。

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

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

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

从某种意义上说，我认为问题有点误导了。关于深度优先搜索的现实世界不是什么？深度优先搜索可以做很多事情。

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

我们使用它们来执行SQL路径查找。

我还要说这是艰苦的调试工作，对于一个贫穷的程序员来说，调试起来很容易。

间接递归的一个现实世界例子是问父母是否可以在圣诞节期间购买该视频游戏。爸爸："问妈妈。" ...妈妈："问爸爸"。 [简而言之，"不，但是我们不想告诉我们，以免我们发脾气。"]

解析器和编译器可以递归下降方法编写。这不是最好的方法，因为lex / yacc之类的工具会生成更快，更高效的解析器，但从概念上讲简单易行，因此仍然很常见。

河内的塔

我们可以与之互动：http://www.mazeworks.com/hanoi/

Using recurrence relations, the exact number of moves that this solution requires can be calculated by: 2h ? 1. This result is obtained by noting that steps 1 and 3 take Th ? 1 moves, and step 2 takes one move, giving Th = 2Th ? 1 + 1.
  See: http://en.wikipedia.org/wiki/Towers_of_hanoi#Recursive_solution

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

递归的真实示例

只要可以通过将问题划分为多个子问题来解决问题，则递归是适当的，这些子问题可以使用相同的算法来解决。树和排序列表上的算法是很自然的选择。可以使用二进制空间分区(BSP)树，胖细分或者将世界划分为多个子部分的其他方式来递归解决计算几何(和3D游戏)中的许多问题。

当我们尝试保证算法的正确性时，递归也是合适的。给定一个接受不可变输入并返回结果的函数，该结果是对输入的递归调用和非递归调用的组合，通常可以使用数学归纳法轻松地证明该函数正确(或者不正确)。用迭代函数或者可能会变异的输入来完成此操作通常很棘手。当处理财务计算和其他应用程序中，正确性非常重要时，这可能很有用。

同上有关编译器的评论。自然地，抽象语法树节点适合于递归。使用递归还可以更轻松地处理所有递归数据结构(链接列表，树，图等)。我确实认为，由于现实问题的类型，我们大多数人在放学后就不会经常使用递归，但是最好将其作为一种选择。

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

不递归地解决它将需要很多不必要的代码。递归的问题在于，要跟踪发生的事情并不容易。遵循执行流程时，我们确实必须专心。但是当它起作用时，代码是优雅而有效的。

我认为这确实取决于语言。在某些语言中(例如Lisp)，递归通常是对问题的自然反应(在这种情况下，通常对于语言，编译器已进行了优化以处理递归)。

Lisp中常见的模式是先对列表的第一个元素执行操作，然后对列表的其余部分调用函数以累加一个值或者一个新列表，这是相当优雅且最自然的方法那种语言的东西。在Java中，没有那么多。

人们通常使用递归方法对文档堆栈进行排序。例如，假设我们正在排序100个带有名称的文档。首先按首字母将文件放入一堆，然后对每堆进行分类。

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

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

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

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

我在Cto中编写了一个树，用于处理在表中查找带有6个分段键的默认情况的键(如果key [0]不存在，请使用默认情况并继续)。查找是递归完成的。我尝试了字典词典(如字典)，但很快就变得太复杂了。

我还用C编写了一个公式求值器，该求值器对存储在树中的方程式进行求值以使求值顺序正确。当然，这可能是为问题选择了不正确的语言的情况，但这是一个有趣的练习。

我没有看到很多人做过的事的例子，而是他们使用的图书馆。希望这能给我们一些思考。

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

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

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

要求A：在完全理解要求A之后，实施此功能。

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

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

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

查找质数的方法是递归的。对于生成哈希密钥，用于使用大量因子的各种加密方案非常有用。

你有一幢大厦。
该建筑有20间客房。
从法律上来说，每个房间只能容纳一定数量的人。
工作是自动将人员分配到房间。如果我的房间变满了，我们需要找到一个可用的房间。
由于只有某些房间可以容纳某些人，因此我们还需要注意哪个房间。

例如：

房间1、2、3可以相互滚动。这个房间是为不能独自行走的孩子而设计的，因此我们希望他们远离其他一切，以避免分心和其他疾病(这对年长的人来说不重要，但是到了6个月，这会变得非常糟糕。应该这三个人都饱了，这个人必须被拒绝进入。

房间4、5、6可以相互滚动。这个房间适合对花生过敏的人，因此，他们不能进入其他房间(可能有花生的东西)。如果三个人都吃饱了，请提出警告，询问他们的过敏水平和健康状况，他们可以被授予使用权限。

在任何给定时间，房间都可以改变。因此，我们可以允许7-14号房间成为无花生房。我们不知道要检查多少间客房。

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

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

shop.oreilly.com/product/9780596510046.do

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

(单击第3章"我写过的最漂亮的代码"下的第一个字幕)。

这里有很多数学示例，但是我们需要一个真实的示例，因此，经过一番思考，这可能是我可以提供的最好的示例：

我们发现感染了致命性给定的球菌性感染并迅速修复的人(A型)，只有五分之一的人(被我们称为B型)被永久性感染，但没有发现这种感染。症状，只是充当传播者。

当类型B感染大量类型A时，这会造成非常令人讨厌的破坏波。

任务是追踪所有B型B并免疫以阻止疾病的骨干。不幸的是，我们无法对所有人实行全国范围的治疗，因为A型患者对B型治疗也具有致命的过敏性。

方式是进行社交发现，给定感染者(A型)，选择上周的所有联系人，并在堆上标记每个联系人。当我们测试某个人被感染时，请将其添加到"跟进"队列中。当一个人是B型时，请将其添加到头部的"跟进"中(因为我们想快速停止)。

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

重复此操作，直到被感染人员的队列变为0，然后等待另一次爆发。

(好的，这有点迭代，但是它是解决递归问题的一种迭代方式，在这种情况下，尝试遍历人口群体的广度优先遍历，以发现问题的可能路径，此外，迭代解决方案通常更快，更有效，而我强迫性地在所有地方都取消了递归，这本能地.....该死！

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

检查创建的图像是否将在尺寸限制框中起作用。

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

编写一个函数，将12345.67这样的数字转换为" 123,450美元和67美分"。

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

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

我曾经写过一个XML解析器，如果不进行递归的话，将很难编写。

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

在函数式编程语言中可以找到一些很好的递归示例。在函数式编程语言(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命令)。

我最后一个现实世界的例子很轻率，但是它说明了递归有时是"合适的"。

我使用的是责任链模式，因此Handler对象或者自行处理请求，或者将请求委托给链下。记录链的构造非常有用：

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

我们可能会认为这不是最纯粹的递归，因为尽管该方法调用了"自身"，但每次调用时它都处于不同的实例中。

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

这是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))))

这是评估序列的定义：

(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

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

int kthLargest(list，k，first，last){j =分区(list，first，last)if(k == j)返回list [j] else if(k

在这里，"分区"选择一个枢轴元素，然后一次遍历数据，重新排列列表，以使小于枢轴的项目排在最前面，然后是枢轴，然后是大于枢轴的项目。 " kthLargest"算法与quicksort非常相似，但仅在列表的一侧递归。

对我来说，这是最简单的递归算法，其运行速度比迭代算法快。不管k，它平均使用2 * n个比较。这比运行k遍历数据，每次查找最小值并将其丢弃的幼稚方法要好得多。

阿列霍

递归是一种非常基本的编程技术，它很容易导致很多问题，因此列出它们就像列出所有可以使用某种加法解决的问题一样。只是通过我的欧拉计画的Lisp解决方案，我发现：一个交叉求和函数，一个数字匹配函数，几个用于搜索空间的函数，一个最小的文本解析器，一个将数字拆分成十进制数字列表的函数，一个函数。构造图形，以及遍历输入文件的函数。

问题在于，当今许多主流编程语言(如果不是大多数的话)都没有尾调用优化，因此使用它们进行深度递归是不可行的。这种不足意味着大多数程序员不得不学习这种自然的思维方式，而不得不依赖其他的，可能不太优雅的循环结构。

如果不是为了引起堆栈溢出的实际限制，那么使用迭代的所有事情都会通过递归来完成，这很自然。

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

如果我们有两个不同但相似的序列，并且想要匹配每个序列的组成部分，以便首先优先使用大的连续块，然后再按相同的序列顺序进行操作，则可以递归地分析这些序列以形成一棵树，然后递归地处理该树以使其展平它。

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