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

голоса
121

Одна из тем, которые, кажется, регулярно приходят на списки рассылки и онлайн-дискуссий достоинства (или его отсутствие) делает Computer Science Degree. Аргумент, который, кажется, придумать время и снова для отрицательной стороной является то, что они кодирования для некоторого количества лет, и они никогда не использовали рекурсию.

Таким образом, вопрос:

  1. Что такое рекурсия?
  2. Когда я использовать рекурсию?
  3. Почему люди не используют рекурсию?
Задан 06/08/2008 в 03:29
источник пользователем
На других языках...                            


40 ответов

голоса
86

Есть много хороших объяснения рекурсии в этой теме, это ответ о том, почему вы не должны использовать его в большинстве языков. * В большинстве основных реализаций процедурного языка (то есть все основные реализация C, C ++, Basic, Python , Ruby, Java и C #) итерация намного предпочтительнее рекурсии.

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

  1. пространство вырубленный на стеке для аргументов функции и локальных переменных
  2. аргументов функции копируются в этом новом пространстве
  3. управление переходит к функции
  4. работает код работы функции
  5. Результат функции копируется в возвращаемое значение
  6. стек перематывается в прежнее положение
  7. управление переходит обратно к месту, где была вызвана функция

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

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

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

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

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

Ответил 06/08/2008 d 06:09
источник пользователем

голоса
63

Простой английский пример рекурсии.

A child couldn't sleep, so her mother told her a story about a little frog,
    who couldn't sleep, so the frog's mother told her a story about a little bear,
         who couldn't sleep, so the bear's mother told her a story about a little weasel... 
            who fell asleep.
         ...and the little bear fell asleep;
    ...and the little frog fell asleep;
...and the child fell asleep.
Ответил 04/05/2010 d 17:38
источник пользователем

голоса
49

В наиболее общем смысле информатика, рекурсия это функция, которая называет себя. Скажем, у вас есть сшитая структура списка:

struct Node {
    Node* next;
};

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

int length(const Node* list) {
    if (!list->next) {
        return 1;
    } else {
        return 1 + length(list->next);
    }
}

(Это, конечно, может быть сделано с для цикла, а также, но это полезно в качестве иллюстрации концепции)

Ответил 04/05/2010 d 12:25
источник пользователем

голоса
46

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

Самый простой пример хвостовая рекурсия, где самая последняя строка функции является вызов себе:

int FloorByTen(int num)
{
    if (num % 10 == 0)
        return num;
    else
        return FloorByTen(num-1);
}

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

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

введите описание изображения здесь

Вы можете сделать один из тех, кто очень просто с помощью рекурсии, где вызов стека филиалов в 3-х направлениях:

private void BuildVertices(double x, double y, double len)
{
    if (len > 0.002)
    {
        mesh.Positions.Add(new Point3D(x, y + len, -len));
        mesh.Positions.Add(new Point3D(x - len, y - len, -len));
        mesh.Positions.Add(new Point3D(x + len, y - len, -len));
        len *= 0.5;
        BuildVertices(x, y + len, len);
        BuildVertices(x - len, y - len, len);
        BuildVertices(x + len, y - len, len);
    }
}

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

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

Вывод

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

Ответил 04/05/2010 d 14:33
источник пользователем

голоса
28

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

Канонический пример является обычным для генерации факториала п. Факториал п вычисляется путем умножения всех чисел от 1 до п. Итеративное решение в C # выглядит следующим образом:

public int Fact(int n)
{
  int fact = 1;

  for( int i = 2; i <= n; i++)
  {
    fact = fact * i;
  }

  return fact;
}

Там нет ничего удивительного в итерационном решении, и это должно иметь смысл для тех, кто знаком с C #.

Рекурсивное решение найдено путем распознавания, что п-й факторный п * Факт (п-1). Или, другими словами, если вы знаете, что определенное количество факториал можно вычислить следующий. Вот рекурсивное решение в C #:

public int FactRec(int n)
{
  if( n < 2 )
  {
    return 1;
  }

  return n * FactRec( n - 1 );
}

Первая часть этой функции называется базовым вариантом (или иногда Guard пункта) и что мешает алгоритм от бега навсегда. Он просто возвращает значение 1 , когда функция вызывается со значением 1 или менее. Вторая часть более интересна и известна как рекурсивный шаг . Здесь мы называем тот же метод с немного измененным параметром (мы уменьшаем его на 1) , а затем умножить результат с нашей копией п.

Когда первый обнаружил это может быть своего рода запутанным, так что полезно рассмотреть, как она работает при запуске. Представьте себе, что мы называем FactRec (5). Мы входим в рутину, не подобраны базовый случай, и поэтому мы в конечном итоге, как это:

// In FactRec(5)
return 5 * FactRec( 5 - 1 );

// which is
return 5 * FactRec(4);

Если мы вновь ввести метод с параметром 4 мы снова не остановились на пункте охраны, и поэтому мы в конечном итоге на:

// In FactRec(4)
return 4 * FactRec(3);

Если подставить это значение, возвращаемого в возвращаемом значение выше, мы получаем

// In FactRec(5)
return 5 * (4 * FactRec(3));

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

return 5 * (4 * FactRec(3));
return 5 * (4 * (3 * FactRec(2)));
return 5 * (4 * (3 * (2 * FactRec(1))));
return 5 * (4 * (3 * (2 * (1))));

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

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

Ответил 06/08/2008 d 03:54
источник пользователем

голоса
12

Рекурсия является решение проблемы с функцией, которая называет себя. Хорошим примером этого является факториал функция. Факториал проблема математике, где факториал 5, к примеру, 5 * 4 * 3 * 2 * 1. Эта функция решает эту проблему в C # для положительных целых чисел (не тестировалось - там может быть ошибка).

public int Factorial(int n)
{
    if (n <= 1)
        return 1;

    return n * Factorial(n - 1);
}
Ответил 04/05/2010 d 12:29
источник пользователем

голоса
9

Рассмотрим старую, хорошо известную проблему :

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

Определение НОДА удивительно просто:

определение НОД

где мода является оператором по модулю (то есть, после того, как остаток целочисленного деления).

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

Если вы хотите знать , почему это работает, смотрите в статье Википедии на алгоритме Евклида .

Давайте вычислим НОД (10, 8) в качестве примера. Каждый шаг равен одному только перед ним:

  1. НОД (10, 8)
  2. НОД (10, 10 по модулю 8)
  3. НОД (8, 2)
  4. НОД (8, 8 по модулю 2)
  5. НОД (2, 0)
  6. 2

На первом этапе, 8 не равна нулю, поэтому применяется вторая часть определения. 10 по модулю 8 = 2, потому что 8 переходит в 10 раз с остатком 2. На шаге 3, вторая часть применяется снова, но на этот раз 8 по модулю 2 = 0, так как 2 делит 8 без остатка. На шаге 5, второй аргумент равен 0, так что ответ 2.

Вы заметили , что на левые и правые стороны знака равенства появляется НОД? Математик бы сказать , что это определение является рекурсивным , так как выражение вы определяете рецидивирует внутри его определения.

Рекурсивные определения, как правило, быть элегантным. Например, рекурсивное определение суммы списка

sum l =
    if empty(l)
        return 0
    else
        return head(l) + sum(tail(l))

где headпервый элемент в списке и tailявляется остальной частью списка. Обратите внимание , что sumрецидивирует внутри его определения в конце.

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

max l =
    if empty(l)
        error
    elsif length(l) = 1
        return head(l)
    else
        tailmax = max(tail(l))
        if head(l) > tailmax
            return head(l)
        else
            return tailmax

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

a * b =
    if b = 0
        return 0
    else
        return a + (a * (b - 1))

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

Объединить рода имеет прекрасный рекурсивное определение:

sort(l) =
    if empty(l) or length(l) = 1
        return l
    else
        (left,right) = split l
        return merge(sort(left), sort(right))

Рекурсивные определения все вокруг , если вы знаете , что искать. Обратите внимание на то, как все эти определения имеют очень простые случаи , базовые, например , НОД (т, 0) = т. Рекурсивные случаи сточить на проблему , чтобы добраться до самых простых ответов.

При таком понимании, теперь вы можете оценить другие алгоритмы в статье Википедии о рекурсии !

Ответил 04/05/2010 d 14:58
источник пользователем

голоса
9

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

Например, для вычисления факториала для числа X, можно представить его как X times the factorial of X-1. Таким образом, метод «рекурсивно» , чтобы найти факториал X-1, а затем умножает то , что он получил от Xдать окончательный ответ. Конечно, найти факториал X-1, это будет первым вычислить факториал X-2, и так далее. Базовый вариант будет , когда Xэто 0 или 1, в этом случае он знает , чтобы вернуться 1так 0! = 1! = 1.

Ответил 04/05/2010 d 12:26
источник пользователем

голоса
9
  1. Функция, которая называет себя
  2. Когда функция может быть (легко) разлагаются в простые операции, плюс ту же функцию на некоторой меньшей части проблемы. Я должен сказать, а, что это делает его хорошим кандидатом для рекурсии.
  3. Они делают!

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

int fact(int a) 
{
  if(a==1)
    return 1;

  return a*fact(a-1);
}

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

Ответил 06/08/2008 d 03:35
источник пользователем

голоса
7

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

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

function checkRecursively(Node n) {
    n.Checked = True;
    foreach ( n.Children as child ) {
        checkRecursively(child);
    }
}

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

Вам нужно быть немного осторожным с рекурсией. Если вы получаете в бесконечный рекурсивный цикл, вы получите исключение переполнения стека :)

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

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

Ответил 06/08/2008 d 03:44
источник пользователем

голоса
5

Рекурсия является выражением, прямо или косвенно ссылается на себя.

Рассмотрим рекурсивные акронимы как простой пример:

  • GNU означает GNU не Unix
  • PHP расшифровывается как PHP: Hypertext Preprocessor
  • YAML означает YAML Не Markup Language
  • WINE означает вино не эмулятор
  • VISA означает Международной ассоциации обслуживания Visa

Другие примеры в Википедии

Ответил 04/05/2010 d 12:56
источник пользователем

голоса
5

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

Во-первых, нам нужно два правила:

  1. если множество пусто, количество элементов в наборе равна нулю (Дух!).
  2. если не пусто, то отсчет один плюс количество элементов в наборе после один элемент удаляется.

Предположим, что у вас есть набор, как это: [ххх]. давайте посчитаем, сколько элементов есть.

  1. множество является [ххх], который не пуст, поэтому мы применяем правило 2. число элементов является один плюс число элементов в [хх] (т.е. мы удалили элемент).
  2. множество является [хм], поэтому мы применяем правило 2 раз: один + количество элементов в [х].
  3. множество является [х], который по-прежнему соответствует правилу 2: один + число элементов в [].
  4. Теперь множество [], который соответствует правилу 1: счетчик равен нулю!
  5. Теперь, когда мы знаем ответ на шаге 4 (0), мы можем решить шаг 3 (1 + 0)
  6. Кроме того, теперь мы знаем ответ на шаге 3 (1), мы можем решить шаг 2 (1 + 1)
  7. И, наконец, теперь, когда мы знаем ответ на этапе 2 (2), мы можем решить шаг 1 (1 + 2) и получить количество элементов в [ххх], которая 3. Ура!

Мы можем представить это как:

count of [x x x] = 1 + count of [x x]
                 = 1 + (1 + count of [x])
                 = 1 + (1 + (1 + count of []))
                 = 1 + (1 + (1 + 0)))
                 = 1 + (1 + (1))
                 = 1 + (2)
                 = 3

При применении рекурсивного решения, то, как правило, по крайней мере, 2 правила:

  • основа, простой случай, в котором говорится, что происходит, когда у вас есть «израсходован» все ваши данные. Это, как правило, некоторые вариации «если вы из данных в процессе, ваш ответ X»
  • рекурсивное правило, которое гласит, что произойдет, если вы до сих пор данные. Это, как правило, какой-то правило, которое говорит, что «сделать что-то, чтобы сделать ваш набор данных меньше, и повторно применить правила меньшего набора данных.»

Если мы переводим выше псевдокод, мы получим:

numberOfItems(set)
    if set is empty
        return 0
    else
        remove 1 item from set
        return 1 + numberOfItems(set)

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

Ответил 06/08/2008 d 04:12
источник пользователем

голоса
5

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

Люди избегают рекурсии по ряду причин:

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

  2. Те из нас, кто сократить наши зубы программирования на процедурном или объектно-ориентированном программировании часто говорили, чтобы избежать рекурсии, потому что это чревато ошибками.

  3. Нам часто говорят, что рекурсия медленно. Вызов и возврат из подпрограммы неоднократно включает в себя много стека толкающего и выскакивает, который медленнее, чем зацикливание. Я думаю, что некоторые языки справиться с этим лучше, чем другие, и теми языками, скорее всего, не те, где доминирующая парадигма процедурная или объектно-ориентированный.

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

Ответил 06/08/2008 d 04:12
источник пользователем

голоса
4

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

void f() {
   ... f() ... 
}

или косвенно:

void f() {
    ... g() ...
}

void g() {
   ... f() ...
}

2.) Если использовать рекурсию

Q: Does using recursion usually make your code faster? 
A: No.
Q: Does using recursion usually use less memory? 
A: No.
Q: Then why use recursion? 
A: It sometimes makes your code much simpler!

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

Ответил 11/03/2014 d 10:47
источник пользователем

голоса
4

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

Возьмем, например, факторный:

factorial(6) = 6*5*4*3*2*1

Но это легко увидеть факториал (6) также:

6 * factorial(5) = 6*(5*4*3*2*1).

Так, как правило:

factorial(n) = n*factorial(n-1)

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

В этом примере мы просто сделать особый случай, определив факториал (1) = 1.

Теперь мы видим его снизу вверх:

factorial(6) = 6*factorial(5)
                   = 6*5*factorial(4)
                   = 6*5*4*factorial(3) = 6*5*4*3*factorial(2) = 6*5*4*3*2*factorial(1) = 6*5*4*3*2*1

Так как мы определили факториал (1) = 1, мы достигаем «дна».

Вообще говоря, рекурсивные процедуры состоит из двух частей:

1) рекурсивная часть, которая определяет некоторую процедуру с точки зрения новых входов в сочетании с тем, что вы «уже сделано» с помощью той же процедуры. (то есть factorial(n) = n*factorial(n-1))

2) Базовая часть, которая гарантирует , что процесс не повторяется вечно, придав ему какое - то место , чтобы начать (т.е. factorial(1) = 1)

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

Надеюсь это поможет...

Ответил 04/05/2010 d 14:30
источник пользователем

голоса
4

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

Я также хотел Стив McConnells обсуждение рекурсии в Совершенный код, где он критикует примеры, используемые в Computer Science книг по рекурсии.

Не использовать рекурсию для факториалов или чисел Фибоначчи

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

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

EDIT: Это было не копаться в ответ DAV в - я не видел, что ответ, когда я отправил это

Ответил 04/05/2010 d 12:29
источник пользователем

голоса
3

Пример: рекурсивное определение лестницы является: Лестница состоит из: - один шаг и лестница (рекурсии) - или только один шаг (окончание)

Ответил 04/05/2010 d 14:34
источник пользователем

голоса
3

Ну, это довольно приличное определение у вас есть. И википедии есть хорошее определение слишком. Таким образом, я добавлю еще один (возможно хуже) определение для вас.

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

Ответил 04/05/2010 d 12:27
источник пользователем

голоса
3

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

Ответил 06/08/2008 d 04:32
источник пользователем

голоса
2

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

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

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

Ответил 30/08/2014 d 11:09
источник пользователем

голоса
2

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

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

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

Ответил 04/05/2010 d 17:46
источник пользователем

голоса
2

На простом английском языке: Предположим, что вы можете сделать 3 вещи:

  1. Возьмите одно яблоко
  2. Запишите учетные знаки
  3. Количество знаков учетных

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

start
  Is the table empty?
  yes: Count the tally marks and cheer like it's your birthday!
  no:  Take 1 apple and put it aside
       Write down a tally mark
       goto start

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

Я надеюсь, что это «простой английский» ответ, который вы ищете!

Ответил 04/05/2010 d 14:09
источник пользователем

голоса
1

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

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

Ответил 04/05/2010 d 17:10
источник пользователем

голоса
1

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

Допустим, вы хотите посмотреть слово в словаре. У вас есть операция под названием «Look-Up» в вашем распоряжении.

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

Ложка: существительное - это посуда с круглым шариком на конце. Ложка: глагол - использовать ложку на что-то Ложка: глагол - прижиматься близко сзади

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

Cuddle: глагол - прижиматься UTENSIL: существительное - инструмент, часто едят посуды

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

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

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

равно п равно 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 ... которые могли бы иметь много накладных расходов на него. Таким же образом, если мы находим неясное слово для поиска в словаре, это может занять отрываясь другими словами и сканирование для контекстных подсказок, пока мы не найдем связь мы знакомы с. Рекурсивные методы могут занять много времени, чтобы работать свой путь до конца. Однако, когда они используются правильно, и поняли, что они могут сделать сложную работу на удивлении просто.

Ответил 04/05/2010 d 17:04
источник пользователем

голоса
1

Очень многие проблемы можно рассматривать в двух типах произведений:

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

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

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

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

Ответил 04/05/2010 d 16:29
источник пользователем

голоса
1

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

Например

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

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

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

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

Ответил 04/05/2010 d 16:22
источник пользователем

голоса
1

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

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

В качестве примера, вот функция для выполнения алгоритма в 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)
}

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

Ответил 04/05/2010 d 15:14
источник пользователем

голоса
1

вызов функции себя или использовать свое собственное определение.

Ответил 04/05/2010 d 14:59
источник пользователем

голоса
1

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

например, когда вы работаете на типе

  tree = null 
       | leaf(value:integer) 
       | node(left: tree, right:tree)

структурный рекурсивный алгоритм будет иметь вид

 function computeSomething(x : tree) =
   if x is null: base case
   if x is leaf: do something with x.value
   if x is node: do something with x.left,
                 do something with x.right,
                 combine the results

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

Теперь, когда вы смотрите на целых (ну, натуральные числа), как определено с помощью аксиом Пеано

 integer = 0 | succ(integer)

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

 function computeSomething(x : integer) =
   if x is 0 : base case
   if x is succ(prev) : do something with prev

Слишком-известный факториал функция о наиболее тривиальном примере этой формы.

Ответил 04/05/2010 d 14:53
источник пользователем

голоса
1

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

Предположим, у вас есть три менеджера - Джек, Джон и Морган. Джек управляет 2 программистов, Джон - 3, и Морган - 5. Вы собираетесь дать каждому менеджеру 300 $ и хотите знать, что это будет стоить. Ответ очевиден - но что, если 2 сотрудников Morgan-s также менеджеры?

ЗДЕСЬ приходит рекурсии. Вы начинаете с вершины иерархии. , omelserg@mail.ru стоимость 0 $. Вы начинаете с Джеком, а затем проверить есть ли у него менеджеры как сотрудники. если вы обнаружите какие-либо из них, проверьте, есть ли у менеджеров в качестве сотрудников и так далее. Добавить 300 $ в стоимости летней каждый раз, когда вы найдете менеджер. когда вы закончите с Джеком, перейти к Джону, его сотрудникам, а затем к Моргану.

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

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

Ответил 04/05/2010 d 13:50
источник пользователем

голоса
1

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

В программировании один пример вызова функции внутри себя.

Посмотрите на следующий пример расчета факториала числа:

public int fact(int n)
{
    if (n==0) return 1;
    else return n*fact(n-1)
}
Ответил 04/05/2010 d 13:48
источник пользователем

голоса
1

Рекурсия это процесс, при котором вызов метода iself, чтобы иметь возможность выполнить определенную задачу. Это уменьшает redundency кода. Большинство recurssive функции или методов должна быть condifiton сломать recussive называют то остановить его, называющие себя, если условие выполняется - это препятствует созданию бесконечного цикла. Не все функции подходят для использования рекурсивно.

Ответил 04/05/2010 d 13:42
источник пользователем

голоса
1

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

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

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

В 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;
}
Ответил 04/05/2010 d 13:02
источник пользователем

голоса
1

«Если у меня есть молоток, сделать все выглядеть, как гвоздь.»

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

пример

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

  1. Разделить: Spread все листы, так что у вас есть только один лист в каждом «стек».
  2. Завоевать:
    1. Обойдите, помещая каждый лист поверх одного другого листа. Теперь у вас есть стеки 2.
    2. Обойдите, помещая каждый 2-стек поверх другой 2-стеки. Теперь у вас есть стеки 4.
    3. Обойдите, помещая каждый 4-стек поверх другой 4-стеки. Теперь у вас есть стеки 8.
    4. ... снова и снова ...
    5. Теперь у вас есть один огромный стек 1024 листов!

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

Ответил 04/05/2010 d 12:54
источник пользователем

голоса
1

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

Ответил 04/05/2010 d 12:25
источник пользователем

голоса
1

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

Ответил 21/08/2008 d 14:18
источник пользователем

голоса
1

Марио, я не понимаю, почему вы использовали рекурсию для этого примера .. Почему не просто цикл по каждой записи? Что-то вроде этого:

String ArrangeString(TStringList* items, String separator)
{
    String result = items->Strings[0];

    for (int position=1; position < items->count; position++) {
        result += separator + items->Strings[position];
    }

    return result;
}

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

Ответил 06/08/2008 d 04:19
источник пользователем

голоса
0

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

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

Поскольку эта версия Tail Рекурсивной

Ответил 21/08/2008 d 14:39
источник пользователем

голоса
0

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

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

  1. Sitemaps - рекурсия через файловую систему , начиная с корневым каталогом документов
  2. пауки - ползком через веб - сайт , чтобы найти адрес электронной почты, ссылки и т.д.
  3. ?
Ответил 06/08/2008 d 04:13
источник пользователем

голоса
0

Я создал рекурсивную функцию , чтобы сцепить список строк с разделителем между ними. Я использую его в основном для создания выражений SQL, пропускание списка полей как « элементы » и « запятая + пробел » в качестве разделителя. Вот функция (Он использует некоторые типы данных родных Borland Builder, но может быть адаптирован к любой другой среде):

String ArrangeString(TStringList* items, int position, String separator)
{
  String result;

  result = items->Strings[position];

  if (position <= items->Count)
    result += separator + ArrangeString(items, position + 1, separator);

  return result;
}

Я называю это следующим образом:

String columnsList;
columnsList = ArrangeString(columns, 0, ", ");

Представьте , у вас есть массив с именем « поля » с этими данными внутри него: « ALBUMNAME », « ReleaseDate », « labelId ». Затем вызовите функцию:

ArrangeString(fields, 0, ", ");

Поскольку функция начинает работать, то «переменная результата » принимает значение 0 позиции массива, который является « ALBUMNAME ».

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

ArrangeString(fields, 1, ", ");

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

Понял? Если у вас нет, у меня есть еще один способ объяснить это. : О)

Ответил 06/08/2008 d 04:00
источник пользователем

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more