在文件系统中使用目录结构怎么样? 递归查找文件、删除文件、创建目录等等。

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


}

快速排序 、 merge sort和大多数其他 N- 对数 N 排序。

在游戏开发(和其他类似领域)中，递归被用于像 BSP 树这样的碰撞侦测。

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

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

由于从处理和内存角度来看，递归代价很高，因此通常只有在拓扑发生更改并且结果以修改过的预先排序列表格式存储时才执行此步骤。

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

当然，很多编译器都大量使用递归。计算机语言本身就是递归的(也就是说，你可以将‘ if’语句嵌入到其他‘ if’语句中，等等)。

用递归方法解决的“现实世界”问题是嵌套娃娃，你的函数是 OpenDoll ()。

给定一堆这样的玩偶，您可以递归地打开这些玩偶，如果愿意，可以调用 OpenDoll () ，直到到达最内层的玩偶。

递归经常在 回溯算法的实现中使用。对于这种“现实世界”的应用程序，数独游戏解决者怎么样？

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

• 解析 XML文件。
• 多维空间中的高效搜索，如二维四叉树、三维八叉树、 kd 树等。
• 分层聚类。
• 仔细想想，遍历任何层次结构都自然而然地适合于递归。
• 在模板超编程中，没有循环，递归是唯一的方法。

假设您正在为一个网站构建一个 CMS，在这个网站中，您的页面是一个树形结构，比方说，根是主页。

假设你的{ user | client | customer | boss }要求你在每个页面上放置一个面包屑导航来显示你在树中的位置。

对于任何给定的页 n，您可能需要遍历到 n 的父节点及其父节点，等等，以递归方式构建一个返回到页树根节点的节点列表。

当然，在这个示例中，每个页面都要多次命中 db，所以可能需要使用一些 SQL 别名，将 page-table 查找为 a，将 page-table 再次查找为 b，并将 a.id 与 b.rent 连接起来，这样就可以让数据库执行递归连接。已经有一段时间了，所以我的语法可能帮不上什么忙。

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

不管怎样，那是我的0.02美元

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

这是我编码的东西。 递归很简单。

我刚刚编写了一个递归函数，以确定是否需要使用 DataContractSerializer 序列化类。最大的问题出现在模板/泛型中，其中一个类可能包含需要被数据契约序列化的其他类型... ... 因此，如果它不是 datacontractSeries，那么它将遍历每个类型，检查它的类型。

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

我认为你的问题在某种意义上有点误导。深度优先搜索有什么不真实的？你可以用深度优先搜索做很多事。

例如，我想给出的另一个例子是递归下降编译。对于许多实际编译器来说，这已经是一个非常现实的问题了。但是你可以说它是 DFS，它基本上是深度优先搜索一个有效的解析树。

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

我还要说的是，调试是一项艰巨的任务，对于一个差劲的程序员来说，很容易把它搞砸。

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

Parsers and compilers may be written in a recursive-descent method. Not the best way to do it, as tools like lex/yacc generate faster and more efficient parsers, but conceptually simple and easy to implement, so they remain common.

河内塔

这里有一个你可以互动的: http://www.mazeworks.com/hanoi/

使用递推关系，这个解决方案所需要的确切步数可以计算为: 2h-1。这个结果是通过注意步骤1和步骤3采取 Th-1步骤，步骤2采取一步骤，给出 Th = 2Th-1 + 1。 参见: < a href = “ http://en.wikipedia.org/wiki/Towers _ of _ hanoi # Recursive _ Solution”rel = “ nofollow norefrer”> http://en.wikipedia.org/wiki/towers_of_hanoi#recursive_solution

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

一个真实的递归例子

Recursion is appropriate whenever a problem can be solved by dividing it into sub-problems, that can use the same algorithm for solving them. Algorithms on trees and sorted lists are a natural fit. Many problems in computational geometry (and 3D games) can be solved recursively using 二分空间划分 (BSP) trees, 脂肪细分, or other ways of dividing the world into sub-parts.

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

关于编译器的注释也是如此。抽象语法树节点自然而然地适合于递归。所有递归数据结构(链表、树、图等)也更容易用递归处理。我确实认为，我们中的大多数人一旦离开学校就不会经常使用递归，因为现实世界中的问题类型很多，但是意识到递归是一种选择是件好事。

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

不用递归就能解决这个问题，需要很多不必要的代码。递归的问题在于不容易跟踪发生的事情。在跟随执行流程时，您确实需要集中精力。但是当它工作时，代码是优雅和有效的。

我认为这真的取决于语言。在某些语言中，例如 口齿不清，递归通常是对问题的自然反应(在这种情况下，编译器通常会优化以处理递归)。

Lisp 中的常见模式是对列表的第一个元素执行操作，然后对列表的其余部分调用函数，以便累积一个值或者一个新列表，这是用该语言完成许多事情的最优雅和最自然的方式。在 爪哇咖啡里，就不是这样了。

人们经常使用递归方法对文档堆栈进行排序。例如，假设您正在对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);
}
}

我用 C # 编写了一个树来处理一个表的查找，这个表有一个带缺省大小写的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 或制图学的几何计算，如寻找圆的边缘。

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

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

You have a building. 这栋楼有20个房间。 法律规定，每个房间只能有一定数量的人。 你的工作是自动分配人员到一个房间。如果我的房间满了，你需要找一个空房间。 鉴于只有特定的房间可以容纳特定的人，您还需要注意哪个房间。

For example:

1,2,3号房间可以滚到一起。这个房间是为那些不能自己走路的孩子准备的，所以你希望他们远离其他事物，以避免分心和其他疾病(这对老年人来说不是一件事，但是对于六个月大的孩子来说，这可能会变得非常糟糕。如果三个人都满了，就不能让他进来。

4号，5号，6号房间可以滚到一起。这个房间是为那些对花生过敏的人准备的，因此，他们不能进入其他房间(那里可能有花生的东西)。如果他们三个都满了，提供一个警告，询问他们的过敏程度和可能性，他们可以获准进入。

在任何给定的时间，房间可以改变。所以你们可以允许7-14号房间没有花生。你不知道要检查多少房间。

Or, perhaps you want to seperate based on age. Grade, gender, etc. 这些只是我遇到的几个例子。

我所知道的最好的例子是 快速排序，它使用递归非常简单:

Shop.oreilly.com/product/9780596510046.do

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

(点击第三章下面的第一个副标题: “我写过的最漂亮的代码”)。

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

你会发现一个人感染了传染性疾病，这是非致命的，并迅速自我修复(A 型) ，除了五分之一的人(我们称之为 B 型)永久性感染，没有任何症状，只是作为一个传播者。

当 B 型病毒感染大量 A 型病毒时，就会产生相当恼人的破坏浪潮。

你的任务是找到所有的 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);
}

Write a function that translates a number like 12345.67 to "twelve thousand three hundred forty-five dollars and sixty-seven cents."

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

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 解析器，如果没有递归，编写起来会困难得多。

我想您总是可以使用堆栈 + 迭代，但是有时候递归实在是太优雅了。

在 functional programming语言中可以找到一些很好的递归例子。在函数式编程语言(二郎、 Haskell、 ML/奥卡姆/F # 等)中，使用递归进行任何列表处理都是很常见的。

当使用典型的命令式 OOP 风格语言处理列表时，常常会看到将列表实现为链表([ item1-> item2-> item3-> item4])。然而，在一些函数式编程语言中，您会发现列表本身是递归实现的，其中列表的“头”指向列表中的第一个项，而“尾”指向包含其余项的列表([ item1-> [ item2-> [ item3-> [ item4-> []]]])。我觉得挺有创意的。

This handling of lists, when combined with pattern matching, is VERY powerful. Let's say I want to sum a list of numbers:

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

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

例如，我可能有一个 网址的列表，我认为把每个 URL 链接到的所有 URL 分开，然后我减少所有 URL 的链接总数，为一个页面生成“值”(这是谷歌在 网页排名中采用的方法，你可以在原来的 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)中的控件树。

来自 SICP的著名的 Eval/Apply 循环

_{(来源: Mit.edu)}

Here is the definition of 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 序列的定义:

(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))))

- > apply-> eval-sequence-> eval

求平均情形 O (n)的中值。等价于在 n 个事物的列表中找到 k 个最大的项，其中 k = n/2:

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

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

阿列霍

递归是一种非常基本的编程技术，它可以解决很多问题，所以列出这些问题就像列出所有可以通过使用某种形式的加法来解决的问题一样。在浏览我为 Project Euler 设计的 Lisp 解决方案时，我发现: 一个交叉汇总函数，一个数字匹配函数，几个搜索空格的函数，一个最小文本解析器，一个将数字分割成十进制数字列表的函数，一个构造图形的函数，以及一个遍历输入文件的函数。

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

在使用迭代的地方，如果没有造成堆栈溢出的实际限制，那么使用递归可以更自然地完成所有工作; -)

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

如果你有两个不同但相似的序列，并且想匹配每个序列的组成部分，这样大的连续块首先受到青睐，然后是相同的序列顺序，那么你可以递归地分析这些序列，形成一棵树，然后递归地处理这棵树，使它变平。

Reference: Recursion & Memoization Example Code

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

包含与自身相似的较小部分的物体的典型例子是:

• tree structure (a branch is like a tree)
• 列表(列表的一部分仍然是列表)
• 容器(俄罗斯娃娃)
• 序列(序列的一部分看起来像下一个)
• 一组对象(一个子组仍然是一组对象)

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

一些递归排序算法、树行走算法、映射/约简算法、分而治之算法都是这种技术的例子。

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

• break the problem down into smaller pieces ==> call itself on a smaller subset of the original data),
• 跟踪各个部分是如何分割的 = = > 调用堆栈,
• 将结果缝回 = = > 基于堆栈的返回值

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

1. 大学储蓄计划: 让 A (n) = n 个月后为大学储蓄的金额 A(0) = $500 每个月有50美元存入一个年利率为5% 的账户。

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

既然你似乎不喜欢计算机科学或数学的例子，这里有一个不同的: 电线谜题。

Many wire puzzles involve removing a long closed loop of wire by working it in and out of wire rings. These puzzles are recursive. 其中之一被称为“箭头动力学”。我告诉你，你可以找到它，如果你谷歌“箭头动力线困惑”

这些谜题很像河内的塔楼。

Feedback loops in a hierarchical organization.

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

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

一直到最后。

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

反馈通过每个经理添加他/她自己的反馈回到树上。

最终，所有的反馈都会回到最高领导手中。

这是自然的解决方案，因为递归方法允许在每个级别进行过滤——整理重复内容和删除令人不快的反馈。顶级老板 可以发送一封全球邮件，让每个员工直接向他/她汇报反馈，但是存在“你不能处理真相”和“你被解雇了”的问题，所以递归在这里工作得最好。