Что такое рекурсия и когда я должен использовать ее?

Я использую рекурсию. Что делает, которые имеют отношение к наличию градуса CS... (который я не делаю, между прочим)

Общее использование я нашел:

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

На самом деле лучшее рекурсивное решение для факториала должно быть:

int factorial_accumulate(int n, int accum) {
    return (n < 2 ? accum : factorial_accumulate(n - 1, n * accum));
}

int factorial(int n) {
    return factorial_accumulate(n, 1);
}

, поскольку эта версия Хвост, Рекурсивный

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

рекурсия http://cart.kolix.de/wp-content/uploads/2009/12/infinite-recursion.jpg

Рекурсия - это когда у вас есть операция, которая использует себя. Вероятно, у него будет точка остановки, иначе это продолжалось бы вечно.

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

Твой друг говорит: «Я действительно мог бы налить пудинга прямо сейчас!» Вы не понимаете, что он имеет в виду, поэтому смотрите в словаре слово «ложка», и оно читается примерно так:

Ложка: существительное - посуда с круглой ложкой на конце. Ложка. : verb - использовать ложку на чем-то Spoon: verb - крепко обнимать сзади

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

Cuddle: глагол - обнимать Utensil: существительное - инструмент, часто столовая

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

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

Традиционный приведенный пример - факториал, где факториал 5 равен 1 * 2 * 3 * 4 * 5 (то есть 120). В базовом случае будет 0 (или 1, в зависимости от). Итак, для любого целого числа n вы делаете следующее

is n равно 0? вернуть 1 в противном случае вернуть n * (факториал n-1)

давайте сделаем это с примером 4 (который, как мы знаем заранее, равен 1 * 2 * 3 * 4 = 24).

факториал 4 ... это 0? нет, значит, это должен быть факториал 4 * 3 , но какой факториал 3? это 3 * факториал 2 факториал 2 равен 2 * факториал 1 факториал 1 равен 1 * факториал 0 и мы ЗНАЕМ факториал 0! :-D это 1, это определение факториал 1 равен 1 * факториал 0, который был 1 ... поэтому 1 * 1 = 1 факториал 2 равен 2 * факториал 1 , который был 1 ... так что 2 * 1 = 2 факториал 3 равен 3 * факториал 2, который был 2 ... поэтому 3 * 2 = 6 факториал 4 (наконец !!) - это 4 * факториал 3, который был 6 ... 4 * 6 = 24

Факториал - это простой случай «базового случая и использует сам себя».

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

Множество проблем можно разделить на два типа:

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

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

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

struct Tree {
    int leaf;
    Tree *leftBranch;
    Tree *rightBranch;
};

Самый простой способ распечатать это - использовать рекурсию:

function printTreeInOrder(Tree *tree) {
    if (tree->leftBranch) {
        printTreeInOrder(tree->leftBranch);
    }
    print(tree->leaf);
    if (tree->rightBranch) {
        printTreeInOrder(tree->rightBranch);
    }
}

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

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

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

это способ делать что-то снова и снова бесконечно, так что используются все опции.

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

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

в C # у вас будет что-то вроде этого:

private void findlinks(string URL, int reccursiveCycleNumb)    {
   if (reccursiveCycleNumb == 0)
        {
            return;
        }

        //recursive action here
        foreach (LinkItem i in LinkFinder.Find(URL))
        {
            //see what links are being caught...
            lblResults.Text += i.Href + "<BR>";

            findlinks(i.Href, reccursiveCycleNumb - 1);
        }

        reccursiveCycleNumb -= reccursiveCycleNumb;
}

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

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

В качестве примера приведем функцию для выполнения алгоритма быстрой сортировки в Scala ( скопировано из статьи в Википедии для Scala )

def qsort: List[Int] => List[Int] = {
  case Nil => Nil
  case pivot :: tail =>
    val (smaller, rest) = tail.partition(_ < pivot)
    qsort(smaller) ::: pivot :: qsort(rest)
}

В этом случае условием выхода является пустой список.

Рекурсия - это техника определения функции, множества или алгоритма в терминах самого себя.

Например,

n! = n(n-1)(n-2)(n-3)...........*3*2*1

Теперь рекурсию можно определить следующим образом:-

n! = n(n-1)!   for n>=1

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