реальный пример рекурсии

Как насчет всего, что связано со структурой каталогов в файловой системе. Рекурсивный поиск файлов, удаление файлов, создание каталогов и т. д.

вот реализация 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());
            }
        }       
    }

}

Quicksort,сортировка слиянием, и большинство других N-log N сортов.

пример Мэтта Дилларда хорош. В более общем плане, любое хождение по дереву может быть очень легко обработано рекурсией. Например, компиляция деревьев синтаксического анализа, прогулка по 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);
    }
}

известный Eval / применить цикл от SICP

вот определение 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-последовательности:

(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 документов с именами на них. Сначала поместите документы в стопки по первой букве, затем отсортируйте каждую стопку.

поиск слов в словаре часто выполняется методом двоичного поиска, который является рекурсивным.

в организациях начальники часто отдают команды начальникам отделов, которые в свою очередь отдают команды руководителям и так далее.

синтаксические анализаторы и компиляторы могут быть записаны в методе рекурсивного спуска. Не лучший способ сделать это, так как такие инструменты, как lex/yacc, генерируют более быстрые и эффективные Парсеры, но концептуально просты и просты в реализации, поэтому они остаются общими.

требование реального мира я получил недавно:

требование A: реализовать эту функцию после полного понимания требования A.

рекурсия применяется к задачам (ситуациям), где вы можете разбить ее (уменьшить ее) на более мелкие части, и каждая часть(ы) выглядит аналогично исходной проблеме.

хорошие примеры того, где вещи, которые содержат меньшие части, похожие на себя:

• дерево (ветка дерева)
• списки (часть списка по-прежнему является списком)
• контейнеры (русские куклы)
• последовательности (часть последовательности выглядит как далее)
• группы объектов (подгруппа-это все еще группа объектов)

Рекурсия-это метод, позволяющий разбивать проблему на все более мелкие кусочки, пока один из этих кусочков не станет достаточно маленьким, чтобы быть куском пирога. Конечно, после того, как вы их разбили, вам нужно "сшить" результаты вместе в правильном порядке, чтобы сформировать полное решение вашей исходной проблемы.

некоторые рекурсивные алгоритмы сортировки, хождение по деревьям алгоритмы, алгоритмы map / reduce, divide-and-conquer-все это примеры этой техники.

в компьютерном программировании большинство стековых языков типа call-return уже имеют встроенные возможности для рекурсии: т. е.

• разбейте задачу на более мелкие части = = > вызовите себя на меньшем подмножестве исходных данных),
• следите за тем, как части делятся ==> стек вызовов,
• сшить результаты обратно = = > на основе стека возвратить

У меня есть система, которая использует чистый хвостовая рекурсия в нескольких местах для имитации состояния машины.

некоторые замечательные примеры рекурсии находятся в функциональное программирование языки. В функциональных языках программирования (Эрланг,Haskell,мл/ OCaml/F# и т. д.), очень часто любая обработка списка использует рекурсию.

при работе со списками в типичных императивных языках ООП очень часто можно увидеть списки, реализованные в виде связанных списков ([item1 - > item2 - > item3 -> item4]). Однако в некоторых функциональных языках программирования вы обнаружите, что сами списки реализуются рекурсивно, где "голова" списка указывает на первый элемент в списке, а "хвост" указывает на список, содержащий остальные элементы ([item1 -> [item2 -> [item3 - > [item4 -> []]]]]). На мой взгляд, это довольно креативно.

эта обработка списков, в сочетании с сопоставлением шаблонов, является очень мощным. Допустим, я хочу суммировать список номера:

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

это по существу говорит:" если мы были вызваны с пустым списком, верните 0 " (что позволяет нам разбить рекурсию), иначе верните значение head + значение Sum, вызванное с оставшимися элементами (следовательно, наша рекурсия).

например, у меня есть список URLs, Я думаю, разбить все URL-адреса каждый URL ссылки, а затем я уменьшить общее количество ссылок на / из всех URL-адресов для создания "значения" для страницы (подход, который Google берет с PageRank и что вы можете найти определенные в оригинале MapReduce документ). Вы можете сделать это, чтобы генерировать количество слов в документе. И многое, многое, многое другое тоже.

вы можете расширить этот функциональный шаблон для любого типа MapReduce код, в котором вы можете взять список чего-то, преобразовать его и вернуть что-то еще (будь то другой список или какая-то команда zip в списке).

XML, или обход всего, что является деревом. Хотя, честно говоря, я почти никогда не использую рекурсию в своей работе.

петли обратной связи в иерархической организации.

топ-босс говорит топ-менеджерам собирать отзывы от всех в компании.

каждый исполнитель собирает своих подчиненных и говорит им, чтобы собрать обратную связь от своих подчиненных.

и дальше по очереди.

люди без прямых отчетов -- листовые узлы в дереве -- дают свои отзывы.

обратная связь перемещается обратно по дереву с каждым добавлением менеджера его / ее собственная обратная связь.

В конце концов вся обратная связь делает его обратно к главному боссу.

Это естественное решение, потому что рекурсивный метод позволяет фильтровать на каждом уровне-сопоставление дубликатов и удаления оскорбительных отзывов. Главный босс может отправить глобальную электронную почту и иметь каждый сотрудник отчет обратной связи непосредственно к нему / ей, но есть "вы не можете справиться с правдой" и" Вы уволены " проблемы, так что рекурсия работает здесь лучше всего.

Предположим, вы создаете CMS для веб-сайта, где ваши страницы находятся в древовидной структуре, причем, скажем, корень является домашней страницей.

предположим также, что ваш {user / client|customer / boss} запрашивает, чтобы вы разместили след хлебной крошки на каждой странице, чтобы показать, где вы находитесь в дереве.

для любой заданной страницы n вы можете подойти к родительскому элементу n и его родительскому элементу и т. д. рекурсивно построить список узлов до корня дерева страниц.

Of конечно, вы нажимаете БД несколько раз на страницу в этом примере, поэтому вы можете использовать некоторые псевдонимы SQL, где вы смотрите таблицу страниц как a, а таблицу страниц снова как b и присоединяетесь a.id с помощью B. parent вы заставляете базу данных выполнять рекурсивные соединения. Это было некоторое время, так что мой синтаксис, вероятно, не поможет.

опять же, вы можете просто рассчитать это только один раз и сохранить его с записью страницы, только обновляя его, если вы переместите страницу. Это, вероятно, будет больше эффективный.

в любом случае, это мои $.02

организация дерево с N уровнями. Несколько узлов проверяются, и вы хотите развернуть только те узлы, которые были проверены.

Это то, что я на самом деле закодированы. Его приятно и легко с рекурсией.

в моей работе у нас есть система с общей структурой данных, которую можно описать как дерево. Это означает, что рекурсия является очень эффективным методом для работы с данными.

решение его без рекурсии потребует много ненужного кода. Проблема с рекурсией заключается в том, что нелегко следить за тем, что происходит. Вы действительно должны сосредоточиться, когда следуете за потоком исполнения. Но когда он работает, код элегантен и эффективен.

расчеты для финансов / физики, такие как составные средние.

• анализ XML.
• эффективный поиск в многомерных пространствах. Например, quad-деревья в 2D, oct-деревья в 3D, KD-деревья и т. д.
• иерархическая кластеризация.
• подумайте об этом, прохождение любой иерархической структуры естественно поддается рекурсии.
• шаблон метапрограммирования в C++, где нет циклов и рекурсия является единственным способом.

разбор дерева элементов управления в Windows Forms или WebForms (.NET Windows Forms/ASP.NET).

лучший пример, который я знаю, это quicksort, это намного проще с рекурсией. Взгляните на:

shop.oreilly.com/product/9780596510046.do

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

(нажимаем на первый подзаголовок в главе 3: "Самый красивый код, который я когда-либо писал").

телефонные и кабельные компании поддерживают модель своей топологии проводки, которая по сути представляет собой большую сеть или график. Рекурсия является одним из способов обхода этой модели, когда вы хотите найти все родительские или все дочерние элементы.

индуктивное рассуждение, процесс образования понятий, носит рекурсивный характер. Ваш мозг делает это все время, в реальном мире.

то же самое замечание о компиляторах. Узлы абстрактного синтаксического дерева естественно поддаются рекурсии. Все рекурсивные структуры данных (связанные списки, деревья, графы и т. д.) также более легко обрабатываются с рекурсией. Я действительно думаю, что большинство из нас не часто используют рекурсию, когда мы выходим из школы из-за типов реальных проблем, но хорошо знать об этом как о варианте.

умножение натуральных чисел является реальным примером рекурсии:

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