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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.69
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
29.07.2010, 04:58     По поводу рекурсии #1
Обязательно ли использовать, если рекурсивно проще чем итеративно или же нет? Пытаюсь полностью понять рекурсию и как-то не особо понимаю. Следует ли полностью ее понять или же предпочесть итеративный подход?

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

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

C++ По поводу грамматики
C++ По поводу нового стандарта Си++
C++ Вопрос по поводу кода
C++ По поводу дерева
C++ По-поводу кейлоггера
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
29.07.2010, 05:08     По поводу рекурсии #2
Золотая середина

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

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

Если возможно такое сравнение, то я бы сравнил с необходимостью применения оператора goto.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
29.07.2010, 05:10  [ТС]     По поводу рекурсии #3
fasked, Сегодня читал у Шилдта почему не следует употреблять goto... Но все же. Бывают ведь такие ситуации, что это проще и логически, и лучше по производительности. Почему же не употреблять тогда? Только потому, что можно обойтись без нее?
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 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);
но опять же к чему это все, если числа небольшие и разницы мы даже не заметим.

Конечно скуповат примерчик получился, но смысл в том, что надо от конкретной ситуации отталкиваться. Если намного проще написать рекурсивную функцию, то зачем тратить время на разработку аналогичной, но без рекурсии. Сделай прикидку, насколько глубокой будет рекурсия и насколько много времени ты потратишь.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
29.07.2010, 05:29  [ТС]     По поводу рекурсии #5
fasked, Ну я про goto говорил) Но да ладно) За пример с рекурсией спасибо.
NightmareZ
 Аватар для NightmareZ
1336 / 559 / 37
Регистрация: 31.03.2009
Сообщений: 1,907
29.07.2010, 05:33     По поводу рекурсии #6
Цитата Сообщение от Lavroff Посмотреть сообщение
ибо жрет много памяти, за счет создания новых копий функций и их вызовов
Кушает стек. И в определённый момент может настать stack overflow.

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

Цитата Сообщение от Lavroff Посмотреть сообщение
Так как же быть?
Руководстоваться здравым смыслом, интуицией, личными предпочтениями.
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 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 считается, потому что он нарушает принципы структурного программирования. если им злоупотреблять.

как всегда, все должно быть в меру и к месту.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
29.07.2010, 05:38  [ТС]     По поводу рекурсии #8
Значит все-таки желательно понять принцип рекурсии, даже если отдаешь предпочтение итеративному подходу?
NightmareZ
 Аватар для NightmareZ
1336 / 559 / 37
Регистрация: 31.03.2009
Сообщений: 1,907
29.07.2010, 05:40     По поводу рекурсии #9
Цитата Сообщение от Lavroff Посмотреть сообщение
fasked, Сегодня читал у Шилдта почему не следует употреблять goto... Но все же. Бывают ведь такие ситуации, что это проще и логически, и лучше по производительности. Почему же не употреблять тогда? Только потому, что можно обойтись без нее?
Потому что книги Шилдта расчитаны не на гениев программирования. Он учит хорошим и правильным манерам, иногда криво учит, иногда неправильно.

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

Добавлено через 25 секунд
Цитата Сообщение от Lavroff Посмотреть сообщение
Значит все-таки желательно понять принцип рекурсии, даже если отдаешь предпочтение итеративному подходу?
Безусловно. Это же самые азы программирования.
niXman
Эксперт C++
 Аватар для niXman
3133 / 1445 / 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 ( ... ) {
}
но я использовал этот вариант еще до прочтение книжки.
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 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; 
 
    // и так далее
}
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
29.07.2010, 05:48  [ТС]     По поводу рекурсии #12
fasked, Спасибо) Все понял вроде пока что)
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
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
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2294 / 1664 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
29.07.2010, 12:00     По поводу рекурсии #14
Цитата Сообщение от Lavroff Посмотреть сообщение
Сегодня читал у Шилдта почему не следует употреблять goto... Но все же. Бывают ведь такие ситуации, что это проще и логически, и лучше по производительности. Почему же не употреблять тогда?
Потому что неизвестно откуда и при каких обстоятельствах был осуществлен переход на метку.
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
29.07.2010, 14:25     По поводу рекурсии #15
Цитата Сообщение от easybudda Посмотреть сообщение
вот за такое по-моему нужно на пару месяцев компа лишать...
Цитата Сообщение от easybudda Посмотреть сообщение
а вот эта строчка просто не скомпилируется - x/2 не может использоваться в качестве lvalue
easybudda, 5.45 утра да и не это здесь главное. считайте, что это псевдокод.
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16833 / 5254 / 323
Регистрация: 30.03.2009
Сообщений: 14,145
Записей в блоге: 26
29.07.2010, 15:39     По поводу рекурсии #16
Цитата Сообщение от niXman Посмотреть сообщение
но я использовал этот вариант еще до прочтение книжки
Типичный вариант, когда код уродуется из принципа, лишь бы избежать goto. Пример с goto был бы предельно понятен. Пример с throw - в общем случае плохо понятен (особенно если процедура длинная): стороннему человеку потребуется много времени для анализа в какой catch мы попадём и где он находится. Не говоря уж о том, что человек интуитивно начнёт искать выше по стеку, предполагая, что незачем throw и catch писать в одной функции

Цитата Сообщение от NightmareZ Посмотреть сообщение
И в определённый момент может настать stack overflow
По большому счёту это является единственной и очень неприятной опасностью. Ситуацию переполнения стека перехватить нельзя и если оно случится, то программа убивается (средствами ОС). Если в случае обычной нехватки памяти (при вызове malloc, например) можно будет хотя бы сообщение написать, что памяти нет, а в случае переполнения стека программа молча сдохнет. Что ещё хуже - нет способа определить, до каких пор можно делать рекурсию. За исключением непереносимых черезж..ых вариантов

Вот ещё один пример, где без goto можно написать только непонятно
Хороший или плохой тон программирования
niXman
Эксперт C++
 Аватар для niXman
3133 / 1445 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
29.07.2010, 15:53     По поводу рекурсии #17
Цитата Сообщение от Evg Посмотреть сообщение
Типичный вариант, когда код уродуется из принципа, лишь бы избежать goto. Пример с goto был бы предельно понятен. Пример с throw - в общем случае плохо понятен (особенно если процедура длинная): стороннему человеку потребуется много времени для анализа в какой catch мы попадём и где он находится. Не говоря уж о том, что человек интуитивно начнёт искать выше по стеку, предполагая, что незачем throw и catch писать в одной функции
частично согласен..
но есть ситуации, когда goto, ну никак не подходит. к примеру, во вложенных блоках кода могут использоваться локальные переменные классовых типов, смарт поинтеры. классы, в деструкторах, могут очищать другие классы на которые они получили ссылку при инициализации. так же, в деструкторах, может происходить инициализация других классов, и т.д.. таких вариантов очень много. отлов багов, порожденных такой реализацией, будет просто мегаиспытанием для прогера.
так же, не стОит забывать про качество кода. вряд ли какая-то серьезная контора позволит использовать goto в с++ коде.
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16833 / 5254 / 323
Регистрация: 30.03.2009
Сообщений: 14,145
Записей в блоге: 26
29.07.2010, 15:58     По поводу рекурсии #18
Цитата Сообщение от niXman Посмотреть сообщение
но есть ситуации, когда goto, ну никак не подходит. к примеру, во вложенных блоках кода могут использоваться локальные переменные классовых типов, смарт поинтеры. классы, в деструкторах, могут очищать другие классы на которые они получили ссылку при инициализации. так же, в деструкторах, может происходить инициализация других классов, и т.д.. таких вариантов очень много. отлов багов, порожденных такой реализацией, будет просто мегаиспытанием для прогера.
Ситуации могут быть всякие. И в каждой конкретной ситуации надо выбирать оптимальное решение. Всегда вместо goto использовать throw - это обычный маразм, достойный авторов книг, предисловие в которых начинается со слов "мне 72 года и я никогда не занимался программированием, но вот в мои руки попалась студия borland-c++ ..." (цитата не дословная, но смысл сохранён).

Цитата Сообщение от niXman Посмотреть сообщение
так же, не стОит забывать про качество кода. вряд ли какая-то серьезная контора позволит использовать goto в с++ коде.
Если контора запрещает использовать goto, то смело можно увольняться, потому что среди руководителей умных людей там точно нет
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
30.07.2010, 06:48  [ТС]     По поводу рекурсии #19
fasked, По поводу НОД. Сейчас попалась эта задача (любым способом найти НОД двух чисел). Написал вот такой лесапед:

Лесапед
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int Nod (int M, int N)
{
    int Noder=0;
    int max=1;
    if(M>N)
    {
        for(int i=1;i<M;i++)
        {
            if((M%i)==0&&(N%i)==0)
            {
                Noder=i;
                if(Noder>max)
                    max=Noder;
            }
        }
    }
    else
    {
        for(int i=1;i<N;i++)
        {
            if((M%i)==0&&(N%i)==0)
            {
                Noder=i;
                if(Noder>max)
                    max=Noder;
            }
        }
    }
    return max;
}


Это очень плохо, если так написано или как вариант вполне возможно?
П.П.С. По поводу рекурсии... Не понял как оно считает это:
C++
1
2
//        else
//                return Nod(b, a % b);
Так. По поводу кол-ва вызовов прямых и обратных понял
Подаем мы второе число, и остаток от деления первого на второе... Как мы получаем конечный результат?
Так... Если значение a<b меняем их местами...

Я так понимаю все идет вот по этому алгоритму?
НОД(0, n) = n; НОД(m, 0) = m; НОД(m, m) = m;
НОД(1, n) = 1; НОД(m, 1) = 1;
Если m, n чётные, то НОД(m, n) = 2*НОД(m/2, n/2);
Если m чётное, n нечётное, то НОД(m, n) = НОД(m/2, n);
Если n чётное, m нечётное, то НОД(m, n) = НОД(m, n/2);
Если m, n нечётные, то НОД(m, n) = НОД(n, |m - n|).
Если да... То как в данном конкретном случае работает рекурсия? Вполне понимаю как устроен алгоритм. Но КАК это выполняется в рекурсии - не доходит. Может потому что ночь...

Добавлено через 25 минут
Хотя алгоритм тоже не всецело ясен...

Добавлено через 27 минут
Понял как вычисляется рекурсией, если НОД 1 (то есть числа вообще несопоставимы)... Но в некоторых аспектах. Иногда вижу числа, которые просто-напросто не понимаю откуда берутся...

Добавлено через 17 минут
Понял по поводу двух четных относительно. Остались некоторые непонятки.
Понял относительно двух нечетных. Но так же остались некоторые непонятки

Добавлено через 17 минут
Не могу больше... За подробное объяснение, что тут к чему, как что высчитывается, как это программно устроено, желательно с примерами, про то, как что высчитывается... Заранее благодарен!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.07.2010, 09:52     По поводу рекурсии
Еще ссылки по теме:

C++ По поводу статического члена класса и рекурсии
C++ По поводу расширения окна
По поводу процедуры(функции) в С++ C++

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

Или воспользуйтесь поиском по форуму:
Demihalf
Унылый школьник
 Аватар для Demihalf
126 / 60 / 3
Регистрация: 06.11.2009
Сообщений: 354
30.07.2010, 09:52     По поводу рекурсии #20
Lavroff, лесапед у вас интересный и очень необычный... По алгоритму Евклида получается, что НОД(а, б) = НОД(б, ц), где ц = а%б (доказательства ищите в вики). Вот вам и рекурсивная форма. Условие выхода из рекурсии: б == 0. В таком случае возвращается значение а. Иначе продолжаем вычислять НОД рекурсивно для значений б и ц. То же самое можно сделать итеративно.

Если что-то сказал не так, буду рад, если меня кто-то поправит.
Yandex
Объявления
30.07.2010, 09:52     По поводу рекурсии
Ответ Создать тему
Опции темы

Текущее время: 03:38. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru