Рекурсия VS Цикл

Пытаюсь для себя усвоить область рационального применения рекурсии. Требуется помощь.
Давайте рассмотрим на примере некого ряда с рекурсивным соотвношением последующего к предыдущему, ну например есть некий a1=2; ai = 1.325 *ai-1 + 2;(i=2...n)
Задача, допустим найти сумму членов ряда для заданного n.
Можно посчитать по рекурсивному методу, можно по циклу.

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

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

0

Я вижу преимущество рекурсии в том, что некоторые алгоритмы проще реализуются. Например, алгоритмы сортировки.

1

Итерация - от человека
Рекурсия - от бога

1

"точность расчета"
Причем тут точность рассчета?
А по теме -- любые фибоначчи-подобные последовательности более предпочтительно вычислять с помощью цикла, более сложные алгоритмы (например, динамика по подотрезкам) легче реализовывать рекурсией, т.к. многие из них предполагают нестандартный обход порой многомерного массива.
Во многих задачах можно использовать рекурсивный метод "ленивая динамика", когда для каждого значения функции f(x,y) будет соответствующая ячейка в массиве res[x,y] (или для f(x) -- res[x]), что минимизирует время выполнения за счет использования уже подсчитанных значений.
Например, решение вашей задачи считается приемлемым с рекурсией только если используется ленивая динамика:
в начале программы - a[1]:=1; все остальные a[i] -- -1;
затем, вызов функции f(n);
функция f(i) - integer {
если a[i]=-1 то {
a[i]=1.325*f(i-1)+2;}
f=a[i];}
соответственно, после выполнения программы все a от 1 до n будут забиты соответствующими им значениями.
однако, гораздо лучше просто for i=2 to n a[i]=1.325*a[i-1]+2;

0

Сообщение от equinoxe точность расчета" Причем тут точность рассчета?

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

0

результат каждой функции хранится как отдельная переменная (а иначе как вы представляете себе работу рекурсивных функций?).
в некоторых средах есть даже окошко со списком вроде стека функций, где каждый элемент списка представляет собой запись "Название_функции(Аргументы):результ ат"
таким образом, если f(x) = f(y) + f(z), то при подсчете f(x) в памяти хранятся уже три переменные: f(y), f(z) и сам (еще не подсчитанный) f(x).

1

Итерация обладает рядом преимуществ: она требует меньше памяти (которое при рекурсии занимает распухающий стек) + меньше машинного времени (опять же рекурсия тратит его на управление стеком). Вообще, программируя рекурсивную программу нужно много чего предусматривать, всякие переполнения и т.д и т.п. На мой взгляд, учитывать это несколько труднее для программиста, нежели имея дело с итерацией.
Уже это обстоятельство (ресурсоемкость) позволяет программисту сделать выбор в пользу итерации, однако, не всё так просто...
Дело в том, что некоторые алгоритмы построить с помощью итерации очень трудно, в то время как с помощью рекурсии - просто и прозрачно. Кроме того, рекурсия более наглядна и не требует объявления дополнительных переменных цикла.

Лично я, когда программирую, где это возможно использую итерацию. И лишь там, где её использование затруднено - рекурсию. Хотя, признаться, очень люблю рекурсию, если красиво её ввернуть в программе, то она действительно "от Бога".

1

Phantom, Да, действительно Оочень уж красива рекурсия, мне она тоже очень нравится.
Поэтому, я и задумался над оправданностью ее применения

0

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

0

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

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

1

почти по теме
я долго ломал руки и ноги с бинарным деревом, но как ток взял рекурсию всё как поносом снесло=)

0