递归的真实例子

Quicksort,合并排序和大多数其他N-log N种类.

这里有许多蹩脚的例子,但你想要一个真实世界的例子,所以想一想,这可能是我能提供的最好的:

你发现一个人患有特定的感染性疾病,这是非致命性的,并迅速自我修复(A型),除了五分之一的人(我们称之为B型),他们永久感染了它并且没有症状,仅仅是一个吊具.

当类型B感染多种类型A时,这会产生非常恼人的破坏性波浪.

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

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

处理完一个人后,从队列前面选择一个人,并根据需要进行免疫.获取以前未访问的所有联系人,然后测试他们是否被感染.

重复,直到受感染的人的队列变为0,然后等待另一次爆发..

(好吧,这有点迭代,但它是一种解决递归问题的迭代方法,在这种情况下,尝试发现可能的问题路径的群体基础的广泛首次遍历,此外,迭代解决方案通常更快,更有效,我强迫性地去除各地的递归,这本身就变得本能了.......该死的!)

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

递归通常用于回溯算法的实现中.对于这个"真实世界"的应用,一个数独求解器怎么样？

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

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

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

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

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

_{(来源: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- > apply- > eval-sequence- >eval

递归用于诸如BSP树之类的用于游戏开发(和其他类似区域)中的碰撞检测.

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

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

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