Рекурсия без факториала, чисел Фибоначчи и т. Д.

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

1. математический
2. Бесполезно в реальной жизни

Есть ли интересные примеры не математического кода для обучения рекурсии?

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

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

void GetAllFilePaths(Directory dir, List<string> paths)
{
    foreach(File file in dir.Files)
    {
        paths.Add(file.Path);
    }

    foreach(Directory subdir in dir.Directories)
    {
        GetAllFilePaths(subdir, paths)
    }
}

List<string> GetAllFilePaths(Directory dir)
{
    List<string> paths = new List<string>();
    GetAllFilePaths(dir, paths);
    return paths;
}

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

Что нужно подумать:

• файловые системы - это в основном деревья; хорошая задача программирования - извлечь все изображения .jpg из определенного каталога и всех его подкаталогов.
• родословная - по генеалогическому древу найдите количество поколений, которые вам нужно пройти, чтобы найти общего предка; или проверьте, принадлежат ли два человека на дереве одному поколению; или проверьте, могут ли два человека на дереве вступать в брак по закону (зависит от юрисдикции :)
• HTML-подобные документы - преобразование между последовательным (текстовым) представлением документа и деревом DOM; выполнять операции над подмножествами DOM (может быть, даже реализовать подмножество xpath?); ...

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

https://stackoverflow.com/questions/105838/real-world-examples-of-recursion

• моделирование заразной инфекции
• генерирующая геометрия
• управление каталогами
• сортировка

https://stackoverflow.com/questions/2085834/how-did-you-practically-use-recursion

• трассировка лучей
• шахматы
• парсинг исходного кода (грамматика языка)

https://stackoverflow.com/questions/4945128/what-is-a-good-example-of-recursion-other-than-generating-a-fibonacci-sequence

• Поиск BST
• Башни Ханоя
• поиск палиндрома

https://stackoverflow.com/questions/126756/examples-of-recursive-functions

• Дает хорошую англоязычную историю, которая иллюстрирует рекурсию рассказом перед сном.

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

• Сортировка слиянием
• Бинарный поиск
• Обход, вставка и удаление на деревьях (в основном используется в приложениях баз данных)
• Генератор перестановок
• Решатель судоку (с возвратом)
• Проверка орфографии (опять же с возвратом)
• Синтаксический анализ (.eg, программа, преобразующая префикс в постфиксную нотацию)

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

Сортировка, определенная рекурсивно в Python.

def sort( a ):
    if len(a) == 1: return a
    part1= sort( a[:len(a)//2] )
    part2= sort( a[len(a)//2:] )
    return merge( part1, part2 )

Слияние, определенное рекурсивно.

def merge( a, b ):
    if len(b) == 0: return a
    if len(a) == 0: return b
    if a[0] < b[0]:
        return [ a[0] ] + merge(a[1:], b)
    else:
        return [ b[0] ] + merge(a, b[1:]) 

Линейный поиск, определенный рекурсивно.

def find( element, sequence ):
    if len(sequence) == 0: return False
    if element == sequence[0]: return True
    return find( element, sequence[1:] )

Бинарный поиск, определенный рекурсивно.

def binsearch( element, sequence ):
    if len(sequence) == 0: return False
    mid = len(sequence)//2
    if element < mid: 
        return binsearch( element, sequence[:mid] )
    else:
        return binsearch( element, sequence[mid:] )

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

Некоторые примеры, не связанные с математикой для обучения рекурсии (по крайней мере, те проблемы, которые я помню со времен обучения в университете):

• Башни Ханоя
• Восемь королев

Это примеры использования Backtracking для решения проблемы.

Другие проблемы - это классика области искусственного интеллекта: поиск по глубине, поиск путей, планирование.

Все эти проблемы связаны с некой «сложной» структурой данных, но если вы не хотите учить ее математике (числам), тогда ваш выбор может быть более ограниченным. Yoy может начать обучение с базовой структуры данных, такой как связанный список. Например, представление натуральных чисел с использованием списка:

0 = пустой список 1 = список с одним узлом. 2 = список с 2 узлами. ...

затем определите сумму двух чисел в терминах этой структуры данных следующим образом: Пусто + N = N Узел (X) + N = Узел (X + N)

Towers of Hanoi - хороший способ научиться рекурсии.

Есть много решений для этого в Интернете на разных языках.

Детектор палиндрома:

Начните со строки: "ABCDEEDCBA" Если начальный и конечный символы равны, тогда повторите и проверьте "BCDEEDCB" и т. Д.

Алгоритм бинарного поиска звучит так, как вы хотите.

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

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

Императивная петля с изменяемой переменной

let xlist = [1;2;3;4;5;6;7;8;9;10]
let mutable sum = 0
for x in xlist do
    sum <- sum + x

Рекурсивный цикл без изменяемого состояния

let xlist = [1;2;3;4;5;6;7;8;9;10]
let rec loop sum xlist = 
    match xlist with
    | [] -> sum
    | x::xlist -> loop (sum + x) xlist
let sum = loop 0 xlist

Следует отметить , что этот вид агрегации будет захвачен в функциях высшего порядка List.foldи может быть написано как List.fold (+) 0 xlistи в самом деле еще проще с функцией удобства , List.sumкак только List.sum xlist.

Я активно использовал рекурсию в игре, играя в AI. При написании на C ++ я использовал серию из примерно 7 функций, которые вызывают друг друга по порядку (первая функция имеет возможность обойти все из них и вместо этого вызвать цепочку из еще 2 функций). Последняя функция в любой цепочке снова вызывала первую функцию до тех пор, пока оставшаяся глубина, которую я хотел найти, не стала равной 0, и в этом случае последняя функция вызывала бы мою функцию оценки и возвращала оценку позиции.

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

Вы можете увидеть очень общую схему программы такого рода, см. Https://secure.wikimedia.org/wikipedia/en/wiki/Minimax#Pseudocode.

Действительно хороший пример из реальной жизни в бизнесе - это так называемый «Билль о материалах». Это данные, которые представляют все компоненты, составляющие готовый продукт. Например, давайте использовать велосипед. Велосипед имеет руль, колеса, раму и т. Д. И каждый из этих компонентов может иметь подкомпоненты. например, колесо может иметь спицы, шток клапана и т. д. Поэтому, как правило, они представлены в виде древовидной структуры.

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

    class BomPart
    {
        public string PartNumber { get; set; }
        public string Desription { get; set; }
        public int Quantity { get; set; }
        public bool Plastic { get; set; }
        public List<BomPart> Components = new List<BomPart>();
    }

И образец рекурсивного вызова ...

    static int ComponentCount(BomPart part)
    {
        int subCount = 0;
        foreach(BomPart p in part.Components)
            subCount += ComponentCount(p);
        return part.Quantity * Math.Max(1,subCount);

    }

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

Семейные отношения служат хорошим примером, потому что все понимают их интуитивно:

ancestor(joe, me) = (joe == me) 
                    OR ancestor(joe, me.father) 
                    OR ancestor(joe, me.mother);

Довольно бесполезная, но демонстрирующая внутреннюю работоспособность рекурсии рекурсивна strlen():

size_t strlen( const char* str )
{
    if( *str == 0 ) {
       return 0;
    }
    return 1 + strlen( str + 1 );
}

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

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

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

Вы просто:

mark your "Current" square
gather a list of free squares that are valid moves
are there no valid moves?
    are all squares marked?
        you win!
for each free square
    recurse!
clear the mark on your current square.
return.    

Многие виды «продуманных» сценариев могут быть реализованы путем тестирования будущих возможностей в таком дереве.