Реальные примеры рекурсии [закрыто]

Question

Что такое реальный мир проблемы, в которых рекурсивный подход является естественным решением, помимо поиска в глубину (DFS)?

(Я не рассматриваю Ханойская башня, Число Фибоначчи, или факториальные задачи реального мира.На мой взгляд, они немного надуманны.)

Answer 1

Здесь много математических примеров, но вы хотели реальный мир пример, итак, немного подумав, это, возможно, лучшее, что я могу предложить:

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

Это создает довольно раздражающие волны хаоса, когда когда-либо тип В заражает множество типов А.

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

Способом, которым вы могли бы это сделать, было бы социальное обнаружение, учитывая инфицированного человека (тип А), выберите все его контакты за последнюю неделю, отметив каждый контакт в куче.Когда вы проверяете, заражен ли человек, добавьте его в очередь "последующих действий".Если человек относится к типу В, добавьте его в раздел "последующие действия" в начале ( потому что вы хотите быстро это прекратить).

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

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

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

Answer 2

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

Answer 3

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

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

}

Answer 4

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

Answer 5

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

Answer 6

Рекурсия часто используется в реализациях Алгоритм обратного отслеживания.Для "реального" применения этого, как насчет Решатель судоку?

Answer 7

Рекурсия уместна всякий раз, когда проблему можно решить, разделив ее на подзадачи, для решения которых может использоваться один и тот же алгоритм.Алгоритмы на деревьях и отсортированных списках подходят естественным образом.Многие задачи в вычислительной геометрии (и 3D-играх) могут быть решены рекурсивно с помощью разбиение двоичного пространства на разделы (BSP) деревья, жировые подразделения, или другие способы разделения мира на составные части.

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

Answer 8

Несомненно, что многие компиляторы активно используют рекурсию.Компьютерные языки сами по своей сути рекурсивны (т. Е. вы можете встраивать операторы 'if' внутрь других операторов 'if' и т.д.).

Answer 9

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

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

Answer 10

Знаменитый цикл оценки / Применения из 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-последовательности:

(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

Answer 11

Рекурсия используется в таких вещах, как BSP-деревья, для обнаружения столкновений в разработке игр (и других подобных областях).

Answer 12

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

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

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

Answer 13

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

Answer 14

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

Требование А:Реализуйте эту функцию после тщательного изучения требования A.

Answer 15

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

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

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

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

Некоторые рекурсивные алгоритмы сортировки, алгоритмы обхода дерева, алгоритмы отображения / сокращения, методы "разделяй и властвуй" - все это примеры этого метода.

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

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

Answer 16

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

Answer 17

Некоторые замечательные примеры рекурсии можно найти в функциональное программирование языки.На функциональных языках программирования (Эрланг, Хаскелл, МЛ/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, вызванное с остальными элементами (следовательно, наша рекурсия).

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

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

Answer 18

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

Answer 19

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

Главный босс приказывает высшим руководителям собирать отзывы от всех сотрудников компании.

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

И так далее по цепочке.

Люди, не имеющие прямых отчетов - конечные узлы в дереве - оставляют свои отзывы.

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

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

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

Answer 20

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

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

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

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

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

В любом случае, это мои 0,02 доллара

Answer 21

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

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

Answer 22

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

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

Answer 23

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

Answer 24

• Анализируя XML файл.
• Эффективный поиск в многомерных пространствах.E.g.quad-деревья в 2D, oct-деревья в 3D, kd-деревья и т.д.
• Иерархическая кластеризация.
• Если подумать, то обход любой иерархической структуры естественным образом приводит к рекурсии.
• Шаблонное метапрограммирование в C ++, где нет циклов и единственным способом является рекурсия.

Answer 25

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

Answer 26

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

shop.oreilly.com/product/9780596510046.do

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

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

Answer 27

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

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

Answer 28

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

Answer 29

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

Answer 30

Умножение натуральных чисел - это реальный пример рекурсии:

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