Реальные примеры рекурсии
Каковы реальные проблемы, в которых рекурсивный подход является естественным решением помимо поиска в глубину (DFS)?
(Я не рассматриваю Ханойскую башню, число Фибоначчи или факторные проблемы реального мира. Они немного придуманы).
55 ответов
Здесь есть много математических примеров, но вы хотели пример из реальной жизни, поэтому, подумав немного, это, пожалуй, лучшее, что я могу предложить:
Вы найдете человека, который заразился данной инфекцией с инфекцией, которая не является фатальной, и быстро исправляется (тип A), за исключением одного из 5 человек (мы будем называть их типом B), которые постоянно заражаются этим вирусом и не показывают никакого симптомы и просто действует распространитель.
Это создает довольно раздражающие волны хаоса, когда тип В заражает множество типов А.
Ваша задача - отследить все типы B и сделать иммунизацию, чтобы остановить костный мозг. К сожалению, вы не можете применить общенациональное лекарство для всех, потому что люди типа А также имеют смертельную аллергию на лекарство, которое работает для типа В.
То, как вы это сделаете, будет социальным открытием, учитывая, что зараженный человек (тип А) выбирает все свои контакты за последнюю неделю, отмечая каждый контакт в куче. Когда вы проверяете, что человек заражен, добавьте его в очередь "следить". Когда человек относится к типу B, добавьте его в заголовок "Продолжить" (потому что вы хотите остановить это быстро).
После обработки данного человека выберите его в начале очереди и при необходимости примените иммунизацию. Получите все их контакты, ранее не посещаемые, и затем проверьте, заражены ли они.
Повторяйте, пока очередь зараженных людей не станет равной 0, а затем дождитесь очередной вспышки..
(Хорошо, это немного итеративно, но это итеративный способ решения рекурсивной задачи, в данном случае это первый обход базы населения, пытающейся обнаружить вероятные пути к проблемам, и, кроме того, итерационные решения часто бывают быстрее и эффективнее и я навязчиво убираю рекурсию везде так сильно, что становлюсь инстинктивным..... черт!)
Как насчет всего, что связано со структурой каталогов в файловой системе. Рекурсивный поиск файлов, удаление файлов, создание каталогов и т. Д.
Вот реализация 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-log N сортировок.
Рекурсия часто используется в реализациях алгоритма Backtracking. Для реального применения этого, как насчет решателя судоку?
Пример Мэтта Дилларда хорош. В более общем смысле, любая прогулка по дереву обычно очень легко справляется с помощью рекурсии. Например, компиляция деревьев разбора, обход XML или HTML и т. Д.
Рекурсия уместна всякий раз, когда проблему можно решить, разделив ее на подзадачи, которые могут использовать один и тот же алгоритм для их решения. Алгоритмы на деревьях и отсортированных списках являются естественным соответствием. Многие проблемы вычислительной геометрии (и трехмерных игр) могут быть рекурсивно решены с использованием деревьев разбиения двоичного пространства (BSP), жирных подразделений или других способов разделения мира на части.
Рекурсия также подходит, когда вы пытаетесь гарантировать правильность алгоритма. Учитывая, что функция принимает неизменяемые входные данные и возвращает результат, представляющий собой комбинацию рекурсивных и нерекурсивных вызовов входных данных, обычно легко доказать, что функция правильная (или нет), используя математическую индукцию. Это часто трудно сделать с помощью итеративной функции или с помощью входных данных, которые могут изменяться. Это может быть полезно при работе с финансовыми расчетами и другими приложениями, где правильность очень важна.
Конечно, многие компиляторы активно используют рекурсию. Компьютерные языки сами по себе являются рекурсивными (т. Е. Вы можете встраивать операторы if в другие операторы if и т. Д.).
Люди часто сортируют пачки документов рекурсивным методом. Например, представьте, что вы сортируете 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);
}
}
Известный цикл Eval/Apply от 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-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
Реальные требования, которые я получил недавно:
Требование A: Реализуйте эту функцию после тщательного понимания требования A.
Рекурсия используется в таких вещах, как деревья BSP, для обнаружения столкновений в разработке игр (и других подобных областях).
Циклы обратной связи в иерархической организации.
Главный босс говорит высшим руководителям собирать отзывы от всех в компании.
Каждый руководитель собирает свои прямые отчеты и говорит им собирать отзывы о своих прямых отчетах.
И дальше по линии.
Люди без прямых отчетов - листовые узлы в дереве - дают свои отзывы.
Обратная связь перемещается обратно вверх по дереву, каждый менеджер добавляет свой собственный отзыв.
В конце концов все отзывы возвращаются к главному боссу.
Это естественное решение, потому что рекурсивный метод позволяет фильтровать на каждом уровне - сортировку дубликатов и устранение наступательных обратных связей. Главный босс может отправить глобальное электронное письмо, и каждый сотрудник сообщит об обратной связи непосредственно ему / ей, но есть проблемы "вы не можете справиться с истиной" и "вы уволены", поэтому рекурсия лучше всего работает здесь.
Рекурсия применяется к задачам (ситуациям), в которых вы можете разбить ее (уменьшить) на более мелкие части, и каждая часть выглядит аналогично исходной проблеме.
Хорошие примеры того, где вещи, которые содержат меньшие части, похожие на себя:
- древовидная структура (ветвь похожа на дерево)
- списки (часть списка - все еще список)
- контейнеры (русские куклы)
- последовательности (часть последовательности выглядит следующим образом)
- группы объектов (подгруппа - это еще группа объектов)
Рекурсия - это метод, позволяющий разбить проблему на мелкие и мелкие кусочки, пока одна из этих фигур не станет достаточно маленькой, чтобы стать куском пирога. Конечно, после того, как вы разбили их, вам нужно "сшить" результаты обратно в правильном порядке, чтобы сформировать полное решение вашей первоначальной проблемы.
Некоторые алгоритмы рекурсивной сортировки, алгоритмы обхода дерева, алгоритмы отображения / сокращения, разделяй и властвуй - все это примеры этой техники.
В компьютерном программировании большинство языков стека с возвратом вызовов уже имеют встроенные возможности для рекурсии:
- разбить проблему на более мелкие части ==> вызывать себя на меньшем подмножестве исходных данных),
- следить за тем, как части делятся ==> стек вызовов,
- сшить результаты обратно ==> стек на основе возврата
У меня есть система, которая использует чистую хвостовую рекурсию в нескольких местах для моделирования конечного автомата.
XML, или обход всего, что является деревом. Хотя, если честно, я почти никогда не использую рекурсию в своей работе.
Парсеры и компиляторы могут быть написаны методом рекурсивного спуска. Не лучший способ сделать это, поскольку такие инструменты, как lex/yacc, генерируют более быстрые и эффективные парсеры, но концептуально просты и легки в реализации, поэтому они остаются общими.
Несколько замечательных примеров рекурсии можно найти в функциональных языках программирования. В функциональных языках программирования ( Erlang, Haskell, ML / 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 в списке).
- Разбор XML- файла.
- Эффективный поиск в многомерных пространствах. Например квад-деревья в 2D, окт-деревья в 3D, kd-деревья и т. д.
- Иерархическая кластеризация.
- Если задуматься, то обход любой иерархической структуры естественным образом поддается рекурсии.
- Шаблонное метапрограммирование в C++, где нет циклов и рекурсия является единственным способом.
Проблема "реального мира", решаемая с помощью рекурсии, - это матрешки. Ваша функция - OpenDoll().
Если бы их было много, вы бы открыли куклы, вызывая OpenDoll (), если хотите, до тех пор, пока не дойдете до самой внутренней куклы.
Лучший пример, который я знаю, это быстрая сортировка, с рекурсией все намного проще. Взгляни на:
http://shop.oreilly.com/product/9780596510046.do
www.amazon.com/Beautiful-Code-Leading-Programmers-Practice/dp/0596510047
(Нажмите на первый подзаголовок под главой 3: "Самый красивый код, который я когда-либо писал").
У вас есть дерево организации, которое имеет N уровней. Несколько узлов проверены, и вы хотите расширить только те узлы, которые были проверены.
Это то, что я на самом деле закодировал. Это хорошо и легко с рекурсией.
Предположим, вы создаете CMS для веб-сайта, где ваши страницы находятся в древовидной структуре, где, скажем, корень является домашней страницей.
Предположим также, что ваши {user|client|customer|boss} требуют, чтобы вы помещали цепочку на каждой странице, чтобы показать, где вы находитесь в дереве.
Для любой данной страницы n вам может потребоваться пройти к родителю n и его родителю и т. Д. Рекурсивно, чтобы построить список узлов обратно до корня дерева страниц.
Конечно, в этом примере вы нажимаете несколько раз на страницу в базе данных, поэтому вы можете использовать псевдонимы SQL, где вы смотрите таблицу страниц как a и таблицу страниц снова как b, и присоединяете a.id с помощью b.parent, поэтому вы заставляете базу данных выполнять рекурсивные объединения. Это было какое-то время, поэтому мой синтаксис, вероятно, не помог.
Опять же, вы можете просто рассчитать это только один раз и сохранить его с записью страницы, обновляя ее только при перемещении страницы. Это, вероятно, будет более эффективным.
Во всяком случае, это мои $.02
Разбор дерева элементов управления в Windows Forms или WebForms (.NET Windows Forms / ASP.NET).
В моей работе у нас есть система с общей структурой данных, которую можно описать как дерево. Это означает, что рекурсия - очень эффективный метод работы с данными.
Решение без рекурсии потребует много ненужного кода. Проблема с рекурсией заключается в том, что нелегко следить за тем, что происходит. Вы действительно должны сосредоточиться, следуя за ходом исполнения. Но когда он работает, код выглядит элегантно и эффективно.
Методы поиска простых чисел рекурсивны. Полезно для генерации хеш-ключей, для различных схем шифрования, которые используют факторы большого числа.
Так же комментарий о компиляторах. Узлы абстрактного синтаксического дерева естественным образом поддаются рекурсии. Все рекурсивные структуры данных (связанные списки, деревья, графики и т. Д.) Также легче обрабатывать с помощью рекурсии. Я действительно думаю, что большинству из нас не удается часто использовать рекурсию, когда мы заканчиваем школу, из-за типов реальных проблем, но хорошо осознавать это как вариант.
Напишите функцию, которая переводит число, подобное 12345,67, в "двенадцать тысяч триста сорок пять долларов и шестьдесят семь центов".