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

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

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

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

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

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

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

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

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

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

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

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

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

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

По поводу защиты от пиратства - C++
День всем добрый! Моя программа имеет такую защиту: при первом запкске программы генерируется лицензионный ключ и записывается в...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
fasked
Эксперт С++
4933 / 2513 / 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 вызовов. а это еще очень неглубокая рекурсия.

Не по теме:

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

ForEveR
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 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 или как?
Вообще что-то ум за разум заходит...

П.С. А чем интересен лесапед?
fasked
Эксперт С++
4933 / 2513 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
30.07.2010, 17:38     По поводу рекурсии #23
Цитата Сообщение от Lavroff Посмотреть сообщение
Главный вопрос. Почему из 5 получается 3?!
там же операция модуля, остаток от деления.
8 % 5 = 3.
Цитата Сообщение от Lavroff Посмотреть сообщение
П.С. А чем интересен лесапед?
большой, два цикла вместо одного. плюс дополнительные переменые. вычилений больше по-моему.
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 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;
}
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 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);
}
Nameless One
Эксперт С++
5769 / 3418 / 255
Регистрация: 08.02.2010
Сообщений: 7,446
01.08.2010, 06:40     По поводу рекурсии #26
Цитата Сообщение от Lavroff Посмотреть сообщение
Максимальное значение переменной, которая передается в функцию 65
65 - это жирно. Уже после 20 будет переполнение типа unsigned long long
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 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. Сам уже не могу
Nameless One
Эксперт С++
5769 / 3418 / 255
Регистрация: 08.02.2010
Сообщений: 7,446
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.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.08.2010, 07:12     По поводу рекурсии
Еще ссылки по теме:

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

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

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

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

Можете подсказать по поводу задачи? - C++
Расчитать сумму членов бесконечного ряда с заданой пользователем точностью E для заданого поьзователем значения х(-1;1) :...


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

Или воспользуйтесь поиском по форуму:
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
01.08.2010, 07:12  [ТС]     По поводу рекурсии #29
Nameless One, Ну да. Это уже ближе к гуголу. П.С. я ведь написал что ошибся) И понял свою ошибку) Но все равно спасибо за пример
Yandex
Объявления
01.08.2010, 07:12     По поводу рекурсии
Ответ Создать тему
Опции темы

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