Форум программистов, компьютерный форум 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
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 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
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 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
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
30.07.2010, 17:38     По поводу рекурсии #23
Цитата Сообщение от Lavroff Посмотреть сообщение
Главный вопрос. Почему из 5 получается 3?!
там же операция модуля, остаток от деления.
8 % 5 = 3.
Цитата Сообщение от Lavroff Посмотреть сообщение
П.С. А чем интересен лесапед?
большой, два цикла вместо одного. плюс дополнительные переменые. вычилений больше по-моему.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 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
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 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
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,390
01.08.2010, 06:40     По поводу рекурсии #26
Цитата Сообщение от Lavroff Посмотреть сообщение
Максимальное значение переменной, которая передается в функцию 65
65 - это жирно. Уже после 20 будет переполнение типа unsigned long long
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 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
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,390
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++ По поводу расширения окна
По поводу процедуры(функции) в С++ C++

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

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

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