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

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

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

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

29.07.2010, 04:58. Просмотров 2036. Ответов 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
Evg
Эксперт CАвтор FAQ
17950 / 6181 / 413
Регистрация: 30.03.2009
Сообщений: 16,972
Записей в блоге: 27
29.07.2010, 15:39 #16
Цитата Сообщение от niXman Посмотреть сообщение
но я использовал этот вариант еще до прочтение книжки
Типичный вариант, когда код уродуется из принципа, лишь бы избежать goto. Пример с goto был бы предельно понятен. Пример с throw - в общем случае плохо понятен (особенно если процедура длинная): стороннему человеку потребуется много времени для анализа в какой catch мы попадём и где он находится. Не говоря уж о том, что человек интуитивно начнёт искать выше по стеку, предполагая, что незачем throw и catch писать в одной функции

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

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

Цитата Сообщение от niXman Посмотреть сообщение
так же, не стОит забывать про качество кода. вряд ли какая-то серьезная контора позволит использовать goto в с++ коде.
Если контора запрещает использовать goto, то смело можно увольняться, потому что среди руководителей умных людей там точно нет
1
ForEveR
В астрале
Эксперт С++
7978 / 4737 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 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 минут
Не могу больше... За подробное объяснение, что тут к чему, как что высчитывается, как это программно устроено, желательно с примерами, про то, как что высчитывается... Заранее благодарен!
0
Demihalf
Унылый школьник
126 / 60 / 3
Регистрация: 06.11.2009
Сообщений: 354
30.07.2010, 09:52 #20
Lavroff, лесапед у вас интересный и очень необычный... По алгоритму Евклида получается, что НОД(а, б) = НОД(б, ц), где ц = а%б (доказательства ищите в вики). Вот вам и рекурсивная форма. Условие выхода из рекурсии: б == 0. В таком случае возвращается значение а. Иначе продолжаем вычислять НОД рекурсивно для значений б и ц. То же самое можно сделать итеративно.

Если что-то сказал не так, буду рад, если меня кто-то поправит.
1
fasked
Эксперт С++
4942 / 2522 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
30.07.2010, 11:27 #21
А что именно непонятно? Просто возьми пример и распиши.
Например вот так, двигаться по стрелкам

Код
Возьмем два числа: 13 и 21.

1f) a = 13, b = 21;          return (2f) ( = 1);
         |                      ^
         v                      |
2f) a = 21, b = 13;          return (3f) ( = 1);
         |                      ^
         v                      |
3f) a = 13, b = 8;           return (4f) ( = 1);
         |                      ^
         v                      |
4f) a = 8,  b = 5;           return (5f) ( = 1);
         |                      ^
         v                      |
5f) a = 5,  b = 3;           return (6f) ( = 1);
         |                      ^
         v                      |
6f) a = 3,  b = 2;           return (7f) ( = 1);
         |                      ^
         v                      |
7f) a = 2,  b = 1;           return (8f) ( = 1);
         |                      ^
         v                      |
8f) a = 1,  b = 1;           return (9f) ( = 1); // 9f - 9-ая вызванная в рекурсии функция nod
         |                      ^
         v                      |
9f) a = 1,  b = 0;           return a ( = 1);
         |                      |
         +----------------------+
Собственно, этим рекурсия и плоха, что пока функция не возвратит значение, она должна держаться в памяти и все переменные в ней тоже хранятся до выхода из функции. конкретно в этом примере необходимо хранить 9 вызовов. а это еще очень неглубокая рекурсия.

Не по теме:

а лесапед и правда очень интересный

1
ForEveR
В астрале
Эксперт С++
7978 / 4737 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
30.07.2010, 17:30  [ТС] #22
4f) a = 8, b = 5;
5f) a = 5, b = 3;
Главный вопрос. Почему из 5 получается 3?! Не могу никак понять действия, когда одно четное, второе нечетное, или наоборот.
По алгоритму Евклида: m четное, n нечетное НОД(m/2, n).
n четное, m нечетное НОД (m, n/2)
Тут первый вариант. т.е.
НОД(4, 5)... Т.к. Нод = 1, то из четырех вычитаем 1 или как?
Вообще что-то ум за разум заходит...

П.С. А чем интересен лесапед?
0
fasked
Эксперт С++
4942 / 2522 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
30.07.2010, 17:38 #23
Цитата Сообщение от Lavroff Посмотреть сообщение
Главный вопрос. Почему из 5 получается 3?!
там же операция модуля, остаток от деления.
8 % 5 = 3.
Цитата Сообщение от Lavroff Посмотреть сообщение
П.С. А чем интересен лесапед?
большой, два цикла вместо одного. плюс дополнительные переменые. вычилений больше по-моему.
1
ForEveR
В астрале
Эксперт С++
7978 / 4737 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
30.07.2010, 19:27  [ТС] #24
fasked, Понял... Спасибо) Ща попробую еще раз пробежаться по разным числам посмотреть

Добавлено через 1 час 23 минуты
Все. Понял. Оказалось, что все намного легче, чем я предполагал.

Все-таки надо перестать искать везде сложности... Думал, что все идет четко по алгоритму Евклида... Сравнивал... А тут оказывается просто остаток от деления в любом случае и если a<b перестановка...

Добавлено через 17 минут
Заодно чуток подшлифовал свой велосипед
Велосипед
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int Nod (int M, int N)
{
    int Noder=0;
    int max=1;
    if(M<N)
    {
        int Temp=M;
        M=N;
        N=Temp;
    }
    for(int i=1;i<=M;i++)
    {
        if((M%i)==0&&(N%i)==0)
        {
            Noder=i;
            if(Noder>max)
                max=Noder;
        }
    }
    return max;
}
0
ForEveR
В астрале
Эксперт С++
7978 / 4737 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
01.08.2010, 06:28  [ТС] #25
Собственно. Если новичкам, желающим понять рекурсию пригодится сея программа будет неплохо.
Вполне доходчиво объясняет что такое рекурсия. Выходные данные вполне неплохо описывают рекурсию вцелом, и рекурсию к этой программе. Максимальное значение переменной, которая передается в функцию 65. Более пока С++ не поддерживает (по крайней мере MSVS 2005).

Факториал с пояснениями
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
31
32
33
34
35
36
37
38
39
//Факториал. Рекурсия
 
#include <iostream>
 
typedef unsigned long long u_ll;
 
int l;
 
u_ll factorial(int);
 
int main()
{
    int n=0;
    std::cout<<"Enter n: ";
    std::cin>>n;
    l=n-1;
    std::cout<< factorial(n) <<'\n';
    return 0;
}
 
u_ll factorial(int n)
{
    static int p=n;
    static u_ll s=p;
    static int count=0;
    if(n<=l)
    {
        count++;
        s*=n;
        std::cout<<"Variable is: "<< p <<std::endl;
        std::cout<<"Var after "<< count <<" step of recourse is: "<< n <<std::endl;
        std::cout<<"Result after "<< count <<" step of recourse is: "<< s <<std::endl;
        std::cout<<std::endl;
    }
    if(n==1)
        return 1;
    else
        return n*factorial(n-1);
}
0
Nameless One
Эксперт С++
5774 / 3424 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
01.08.2010, 06:40 #26
Цитата Сообщение от Lavroff Посмотреть сообщение
Максимальное значение переменной, которая передается в функцию 65
65 - это жирно. Уже после 20 будет переполнение типа unsigned long long
1
ForEveR
В астрале
Эксперт С++
7978 / 4737 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
01.08.2010, 06:54  [ТС] #27
Nameless One, Вы были правы. Где-то после 20+ переполнение пойдет.

После 21.
Факториал 20 - 2.432.902.008.176.640.000
Факториал 21 - 14.197.454.024.290.336.768

Модеры фиксаните плиз сообщение насчет 65. Поставьте там 21. Сам уже не могу
0
Nameless One
Эксперт С++
5774 / 3424 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
01.08.2010, 07:08 #28
Lavroff, посмотри, какую информацию о типе unsigned long long выдает следующая прога:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <limits>
#include <typeinfo>
 
template<class T>
void typeinfo()
{
    std::cout << "Type: \'" << typeid(T).name() << "\'" << std::endl;
    std::cout << "Max value = " << std::numeric_limits<T>::max() << std::endl;
    std::cout << "Min value = " << std::numeric_limits<T>::min() << std::endl;
    std::cout << "Size in bytes = " << sizeof (T) << std::endl;
}
 
int main()
{
    typeinfo<unsigned long long>();
    system("pause");
    return EXIT_SUCCESS;
}
Факториал - это достаточно быстро возрастающая функция. Если 13! уже больше миллиарда, то 65! уже заведомо больше значения, которое выдает numeric_limits<...>::max(). А переполнение, как я говорил, происходит уже для n > 20.

Добавлено через 2 минуты
PS. Калькулятор говорит, что 65! - это число порядка http://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{90}, что уже не влезет даже во всеми нами ожидаемый тип __int128.
1
ForEveR
В астрале
Эксперт С++
7978 / 4737 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
01.08.2010, 07:12  [ТС] #29
Nameless One, Ну да. Это уже ближе к гуголу. П.С. я ведь написал что ошибся) И понял свою ошибку) Но все равно спасибо за пример
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.08.2010, 07:12
Привет! Вот еще темы с ответами:

По поводу процедуры(функции) в С++ - 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++
Здравствуйте, очень хочу узнать. Как в играх делают окно игры на весь экран? И возможно ли это в простых формах. Допустим при запуске...


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

Или воспользуйтесь поиском по форуму:
29
Yandex
Объявления
01.08.2010, 07:12
Ответ Создать тему
Опции темы

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