Как проверить, подходит ли рекурсия или итерация для конкретной программы?

Question

В моем колледже меня попросили написать JAVA-программу для серии Фибоначчи. Я использовал рекурсию для написания этой программы.

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

Как анализировать наш алгоритм? Как проверить пространственную и временную сложность как в итерации, так и в рекурсии? Именно тогда я обнаружил, что эти вещи так же важны, как ИСПРАВНОСТЬ ПРОГРАММЫ.

Answer 1

В thumbrule:

• рекурсии легко понять, для людей. Но это стеки, и стек всегда является конечным ресурсом.
• Итерация является последовательной и в то же время легче отлаживать. Но иногда это может привести к сложным для понимания алгоритмам, которые можно легко сделать с помощью рекурсии.

Таким образом, всякий раз, когда количество шагов ограничено небольшим количеством управляемых номеров, вы можете перейти на рекурсию. Поскольку вы будете уверены, что стек никогда не переполняется и в то же время код рекурсии compact and elegant.

Если вы хотите изучить больше, это может помочь. Recursion vs loops и Recursion or Iteration?

Редактировать Как отметил @MrP, некоторые special рекурсии, могут быть оптимизированы с помощью некоторых компиляторов.

Answer 2

Он не имеет ничего общего со сложностью алгоритма: при использовании рекурсии - каждый вызов создает новый кадр в стеке - так что если рекурсия слишком глубоко вы можете столкнуться с StackOverflow :)

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

Answer 3

Я предлагаю вам перейти по ссылке http://nptel.iitm.ac.in/courses.php?disciplineId=106 и найти несколько лекций по разработке и анализу алгоритмов. Его основная концепция проектирования алгоритмов. Хорошая удача.

Answer 4

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

int fib(int n) { 
    if (n < 2) { return 1; } 
    return fib(n-1) + fib(n-2) 
} 

вы будете вычисления FIB (п-1), который вычисляет FIB (п-2) и FIB (п-3). Но для вычисления fib (n) вы уже вычисляете fib (n-2). Чтобы улучшить это, вам нужно будет сохранить временные результаты. Обычно это проще с использованием итерации и начиная с i = 0, до n. Таким образом, вы можете легко сохранить последние два результата и не перечитывать одни и те же значения снова и снова.

Простой способ убедиться, что алгоритм эффективен, состоит в том, чтобы попытаться решить его для нескольких более сложных примеров. Вы также можете рассчитать его более точно. Возьмите пример фибоначчи выше. Вызов fib (n) займет сложность O(fib(n)) = O(fib(n-1)) +O(fib(n-2)) + 1 (давайте просто возьмем 1 для добавления).Предположим, что O(fib(0)) = O(fib(1)) = 1. Это означает O(fib(2)) = 3, O(fib((3)) = 5, O(fib(4)) = 9. Как вы можете видеть, эта серия будет расти быстрее, чем сама серия фибоначчи! Это означает огромную сложность. Если у вас будет итеративный алгоритм с циклом for от 0 до n, ваша сложность будет масштабироваться в порядке n, что было бы лучше.

Для получения дополнительной информации ознакомьтесь с примечанием большой о.