Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.69
ForEveR
В астрале
Эксперт С++
7979 / 4738 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
#1

По поводу рекурсии - C++

29.07.2010, 04:58. Просмотров 2051. Ответов 28
Метки нет (Все метки)

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

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

Так как же быть?
1
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.07.2010, 04:58
Здравствуйте! Я подобрал для вас темы с ответами на вопрос По поводу рекурсии (C++):

По поводу статического члена класса и рекурсии - C++
Привет! Тут вот небольшой вопросик по поводу. Читаю книжку Страуструпа нашего и возник вопросик. ...

по поводу memset - C++
здравствуйте, есть, допустим, такой код(rtti включен): struct img { virtual void a() = 0; }; struct img_ : public img { ...

По-поводу кейлоггера - C++
Есть-ли такие кейлоггеры которые будут считывать нажатие клавиш в определенном приложении? Чтоб читало исключительно в c.s. (допустим):-[...

По поводу дерева - C++
"Дано дерево поиска, ключи которого – целые числа (положительные и отрицательные). Определить К-е отрицательное число, следующее за ...

По поводу грамматики - C++
Поясните почему следующее не правильно #define TEXT_HELLOW(name) '\"' ## HELLOW##name ## '\"' ... main(...){ ... ...

По поводу нового стандарта Си++ - C++
Всем доброго времени суток:) Меню волнует вопрос по этим нововведениям которые должны будут произойти(C++0x — будущая версия стандарта...

28
fasked
Эксперт С++
4945 / 2525 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
29.07.2010, 05:08 #2
Золотая середина

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

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

Если возможно такое сравнение, то я бы сравнил с необходимостью применения оператора goto.
1
ForEveR
В астрале
Эксперт С++
7979 / 4738 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
29.07.2010, 05:10  [ТС] #3
fasked, Сегодня читал у Шилдта почему не следует употреблять goto... Но все же. Бывают ведь такие ситуации, что это проще и логически, и лучше по производительности. Почему же не употреблять тогда? Только потому, что можно обойтись без нее?
0
fasked
Эксперт С++
4945 / 2525 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
29.07.2010, 05:26 #4
Цитата Сообщение от Lavroff Посмотреть сообщение
Почему же не употреблять тогда? Только потому, что можно обойтись без нее?
Ну почему же сразу не употреблять. Давай попробуем рассмотреть конкретный пример. Самый распространенный с рекурсией вспоминается только нахождение НОД алгоритмом Евклида.

Вот вариант с рекурсией:
C
1
2
3
4
5
6
7
uint nod (uint a, uint b)
{
        if (b == 0)
                return a;
        else
                return nod(b, a % b);
}
вот вариант без рекурсии:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
uint nod(uint m, uint n)
{
    uint r = 0;
 
    r = m % n;
    while(r != 0)
    {
        m = n;
        n = r;
 
        r = m % n;
    }
 
    return n;
}
если брать небольшие числа то разницы в производительности не будет вообще никакой. а если представить, что возможна ситуация, когда вложенность рекурсии достигнет действительно больших размеров, то стоит наверное задуматься. плюс ко всему вариант без рекурсии легко оптимизируется еще одной строкой, уменьшая количество операций. если в самом начале добавить такую проверку:
C
1
2
    if(m < n)
        SWAP(m,n);
но опять же к чему это все, если числа небольшие и разницы мы даже не заметим.

Конечно скуповат примерчик получился, но смысл в том, что надо от конкретной ситуации отталкиваться. Если намного проще написать рекурсивную функцию, то зачем тратить время на разработку аналогичной, но без рекурсии. Сделай прикидку, насколько глубокой будет рекурсия и насколько много времени ты потратишь.
2
ForEveR
В астрале
Эксперт С++
7979 / 4738 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
29.07.2010, 05:29  [ТС] #5
fasked, Ну я про goto говорил) Но да ладно) За пример с рекурсией спасибо.
0
NightmareZ
1360 / 568 / 37
Регистрация: 31.03.2009
Сообщений: 1,939
29.07.2010, 05:33 #6
Цитата Сообщение от Lavroff Посмотреть сообщение
ибо жрет много памяти, за счет создания новых копий функций и их вызовов
Кушает стек. И в определённый момент может настать stack overflow.

В функциональных языках хвостовая рекурсия обычно оптимизируется, разворачиваясь в итеративную форму. Делают ли что-то подобное современные компиляторы C++, я не знаю.

Цитата Сообщение от Lavroff Посмотреть сообщение
Так как же быть?
Руководстоваться здравым смыслом, интуицией, личными предпочтениями.
1
fasked
Эксперт С++
4945 / 2525 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
29.07.2010, 05:36 #7
Цитата Сообщение от Lavroff Посмотреть сообщение
Ну я про goto говорил
ну а про goto классическим примером являются вложенные циклы.
C
1
2
3
4
5
6
7
8
9
10
11
12
for(;;)
{
   for(;;)
   {
      for(;;)
      {
           // здесь наступает условие по которому надо выйти из ВСЕХ! циклов
           // целесообразнее сделать goto
           // чем завести переменную под флаг и в каждом цикле проверять условие
      }
   }
}
таким образом goto делает программу куда понятнее и эффективнее, чем его отсутствие
просто нежелательным исопльзование goto считается, потому что он нарушает принципы структурного программирования. если им злоупотреблять.

как всегда, все должно быть в меру и к месту.
1
ForEveR
В астрале
Эксперт С++
7979 / 4738 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
29.07.2010, 05:38  [ТС] #8
Значит все-таки желательно понять принцип рекурсии, даже если отдаешь предпочтение итеративному подходу?
0
NightmareZ
1360 / 568 / 37
Регистрация: 31.03.2009
Сообщений: 1,939
29.07.2010, 05:40 #9
Цитата Сообщение от Lavroff Посмотреть сообщение
fasked, Сегодня читал у Шилдта почему не следует употреблять goto... Но все же. Бывают ведь такие ситуации, что это проще и логически, и лучше по производительности. Почему же не употреблять тогда? Только потому, что можно обойтись без нее?
Потому что книги Шилдта расчитаны не на гениев программирования. Он учит хорошим и правильным манерам, иногда криво учит, иногда неправильно.

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

Добавлено через 25 секунд
Цитата Сообщение от Lavroff Посмотреть сообщение
Значит все-таки желательно понять принцип рекурсии, даже если отдаешь предпочтение итеративному подходу?
Безусловно. Это же самые азы программирования.
1
niXman
Эксперт С++
3138 / 1450 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
29.07.2010, 05:44 #10
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
по поводу косяков с goto много написано. я никогда не использовал оного.
то ли у Саттера, то ли у Александреску.. не помню, был пример выхода из вложенных циклов в стиле с++:
C++
1
2
3
4
5
6
7
8
9
10
try {
   for(;;) {
      for(;;) {
         for(;;) {
            throw 0;
         }
      }
   }
} catch ( ... ) {
}
но я использовал этот вариант еще до прочтение книжки.
5
fasked
Эксперт С++
4945 / 2525 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
29.07.2010, 05:45 #11
Цитата Сообщение от Lavroff Посмотреть сообщение
Значит все-таки желательно понять принцип рекурсии, даже если отдаешь предпочтение итеративным методам?
я не совсем хорошо сейчас понимаю, что ты подразумеваешь под выражением "принцип рекурсии"
но если ты имеешь в виду, как она работает и зачем она работает, то конечно надо.

еще неплохой по-моему пример с рекурсивным вызовом, когда требуется добиться определенного условия следования аргументов функции.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void foo(int a, int b)
{
    int z, x, c, v, b, n, m; // все эти параметры каким то волшебным образом строго зависят от a и b
                             // но нам необходимо чтобы число a было обязательно меньше числа b
                             // хотя результат вычислений не зависит от порядка следования переменных
 
    if(a > b)
    {
        foo(b, a);
        return;
    }
 
    // здесь присваивание переменных
    z = x/2 = a/2; 
 
    // и так далее
}
2
ForEveR
В астрале
Эксперт С++
7979 / 4738 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
29.07.2010, 05:48  [ТС] #12
fasked, Спасибо) Все понял вроде пока что)
0
easybudda
Модератор
Эксперт CЭксперт С++
9683 / 5633 / 956
Регистрация: 25.07.2009
Сообщений: 10,811
29.07.2010, 11:23 #13
Цитата Сообщение от fasked Посмотреть сообщение
int z, x, c, v, b, n, m;
вот за такое по-моему нужно на пару месяцев компа лишать...

Добавлено через 1 минуту
Цитата Сообщение от fasked Посмотреть сообщение
z = x/2 = a/2;
а вот эта строчка просто не скомпилируется - x/2 не может использоваться в качестве lvalue
2
CyBOSSeR
Эксперт С++
2303 / 1673 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
29.07.2010, 12:00 #14
Цитата Сообщение от Lavroff Посмотреть сообщение
Сегодня читал у Шилдта почему не следует употреблять goto... Но все же. Бывают ведь такие ситуации, что это проще и логически, и лучше по производительности. Почему же не употреблять тогда?
Потому что неизвестно откуда и при каких обстоятельствах был осуществлен переход на метку.
1
fasked
Эксперт С++
4945 / 2525 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
29.07.2010, 14:25 #15
Цитата Сообщение от easybudda Посмотреть сообщение
вот за такое по-моему нужно на пару месяцев компа лишать...
Цитата Сообщение от easybudda Посмотреть сообщение
а вот эта строчка просто не скомпилируется - x/2 не может использоваться в качестве lvalue
easybudda, 5.45 утра да и не это здесь главное. считайте, что это псевдокод.
0
29.07.2010, 14:25
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.07.2010, 14:25
Привет! Вот еще темы с ответами:

По поводу процедуры(функции) в С++ - C++
в Паскале процедура: type m=array of real; procedure SortInc(var a:m; n:byte); var i,j:byte; t:real; begin for i:=1...

По поводу библиотек и их подключения - C++
Добрый день, нужна помощь в подключении библиотеки. Я пишу свою библиотечку, получаю 2 файла mylib.cpp и mylib.h , если кидать в папку...

Вопрос по поводу кода - C++
Здраствуйте я делаю крестики нолики и возник вопрос #include &lt;iostream&gt; using namespace std; void main () { int pole ={0};...

По поводу расширения окна - C++
Здравствуйте, очень хочу узнать. Как в играх делают окно игры на весь экран? И возможно ли это в простых формах. Допустим при запуске...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru