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

У меня проблема с университетской лабораторией;

Напишите короткую программу, которая выводит все возможные строки, используя символы "c", "a", "r", "b", "o" и "n" ровно один раз.

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

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

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

Спасибо,

Источник

6 ответов

Решение

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

В качестве примера, хваленая факториальная функция - это та, где я, вероятно, выбрал бы итеративный подход, когда числа были большими. Подсчет 10000! с:

def factorial (n):
    if n = 1 return 1
    return n * factorial (n-1)

будет использовать 10000 кадров стека (если, конечно, компилятор не оптимизирует их в итеративное решение), довольно много. Итеративное решение:

def factorial (n)
    r = 1
    while n > 1:
        r = r * n
        n = n - 1
    return r

будет использовать только один кадр стека и немного дороже.

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

Ваш carbon Например, я бы использовал рекурсию, так как:

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

Например, следующий код Python делает свое дело:

def recur (str, pref = ""):
    # Terminating condition.

    if str == "":
        print pref
        return

    # Rotate string so all letters get a chance to be first.

    for i in range (len (str)):
        recur (str[1:], pref + str[:1])
        str = str[1:] + str[:1]

recur ("abc")

производство:

abc
acb
bca
bac
cab
cba

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

Источник

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

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

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

Источник

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

Источник

Алгоритмы и структуры данных от Niklaus Wirth имеют раздел "Когда не следует использовать рекурсию", но рекурсия является полезным инструментом программиста. Я думаю, что понимание рекурсии "необходимо" для программиста.

У вас есть умный подход к проблеме перестановки. Это может быть решено рекурсивно (псевдокод):

private void PermutationsRecursive(string prefix, string s)
{
    int N = s.Length;

    if (N > 0)
        for (int i = 0; i < N; i++)
            PermutationsRecursive(prefix + s[i], s.Substring(0, i) + s.Substring(i + 1, N - i - 1));
    else
        WriteLine(prefix);
}

PermutationsRecursive("", "carbon");
Источник

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

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


text = 'carbon'
n = len(text)
for permutation_i in range(factorial(n)):
    free_letters = list(text)
    divisor = 1
    for character_i in range(n, 0, -1):
        letter = free_letters.pop(permutation_i//divisor%character_i)
        print(letter, end='')
        divisor *= character_i
    print()

Источник

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

Источник
Другие вопросы по тегам