По поводу рекурсии

@ForEveR · Регистрация: 24.06.2010

Студворк — интернет-сервис помощи студентам

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

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

Так как же быть?

@fasked · 30.07.2010, 11:27

А что именно непонятно? Просто возьми пример и распиши.
Например вот так, двигаться по стрелкам

Code
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
Возьмем два числа: 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 · 30.07.2010, 17:30 **[ТС]**

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 · 30.07.2010, 17:38

Сообщение от Lavroff

Главный вопрос. Почему из 5 получается 3?!

там же операция модуля, остаток от деления.
8 % 5 = 3.

Сообщение от Lavroff

П.С. А чем интересен лесапед?

большой, два цикла вместо одного. плюс дополнительные переменые. вычилений больше по-моему.

@ForEveR · 30.07.2010, 19:27 **[ТС]**

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 · 01.08.2010, 06:28 **[ТС]**

Собственно. Если новичкам, желающим понять рекурсию пригодится сея программа будет неплохо.
Вполне доходчиво объясняет что такое рекурсия. Выходные данные вполне неплохо описывают рекурсию вцелом, и рекурсию к этой программе. Максимальное значение переменной, которая передается в функцию 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 · 01.08.2010, 06:40

Сообщение от Lavroff

Максимальное значение переменной, которая передается в функцию 65

65 - это жирно. Уже после 20 будет переполнение типа unsigned long long

@ForEveR · 01.08.2010, 06:54 **[ТС]**

Nameless One, Вы были правы. Где-то после 20+ переполнение пойдет.

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

Модеры фиксаните плиз сообщение насчет 65. Поставьте там 21. Сам уже не могу

@Nameless One · 01.08.2010, 07:08

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! - это число порядка $https://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{90}$ , что уже не влезет даже во всеми нами ожидаемый тип __int128.

@ForEveR · 01.08.2010, 07:12 **[ТС]**

Nameless One, Ну да. Это уже ближе к гуголу. П.С. я ведь написал что ошибся) И понял свою ошибку) Но все равно спасибо за пример

Новые блоги и статьи Все статьи Все блоги /
Море в объективе kumehtar 06.07.2026 Хотел написать много проникновенных слов, но передумал. Оно само - говорит. Кто слышит тот слышит.	Оказывается, Unreal Engine позволяет качество на порядки выше, чем было в Lineedge Etyuhibosecyu 05.07.2026 Жаль, конечно, что я не узнал об этом, пока Lineedge существовала, а то бы Noname2331 написал, что волки превращаются в пиксельную кашу, а я бы его попросил скачать какую-нибудь бриллиантовую или Pro. . .	Doom для терминала без стрельбы и монстров. 3D Raycasting на ascii. dcc0 05.07.2026 Попросил нейронную сеть deepai. org написать рейкастинг 3D с библиотекой ncurses для Linux. Чтобы можно было ходить на стрелочки. Чтобы стены были отрисованы символами. Справилась. Первый вариант. . .	Установка статуса документа по условию Maks 05.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "НарядПутевка" разработанного в КА2. Задача: в табличной части "Материалы" документа при записи автоматически устанавливать статус. . .
Сезонность и суточность закисления почв anaschu 04.07.2026 200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .	В чем ценность человеческого опыта в глобальном смысле? kumehtar 03.07.2026 Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .	интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .	Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562

	По поводу рекурсии 29.07.2010, 04:58. Показов 4627. Ответов 28 Метки нет (Все метки) Обязательно ли использовать, если рекурсивно проще чем итеративно или же нет? Пытаюсь полностью понять рекурсию и как-то не особо понимаю. Следует ли полностью ее понять или же предпочесть итеративный подход? Дейтлы пишут, что использовать стоит аккуратно, ибо жрет много памяти, за счет создания новых копий функций и их вызовов, однако в некоторых программах рекурсия может оказаться эффективнее, за счет того, что код станет понятнее. Так как же быть? 1

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	01.08.2010, 06:54 [ТС]
	Nameless One, Вы были правы. Где-то после 20+ переполнение пойдет. После 21. Факториал 20 - 2.432.902.008.176.640.000 Факториал 21 - 14.197.454.024.290.336.768 Модеры фиксаните плиз сообщение насчет 65. Поставьте там 21. Сам уже не могу 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	01.08.2010, 07:12 [ТС]
	Nameless One, Ну да. Это уже ближе к гуголу. П.С. я ведь написал что ошибся) И понял свою ошибку) Но все равно спасибо за пример 0