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

@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, Ну да. Это уже ближе к гуголу. П.С. я ведь написал что ошибся) И понял свою ошибку) Но все равно спасибо за пример

Новые блоги и статьи Все статьи Все блоги /
Саморегулирующийся социальный контракт для сервера cross-section. Hrethgir 14.08.2026 С кодом конечно таких глубоких размышлений пока не было, впрочем я уже привык к алгоритмизации. Суть предмета записи: снова в диалоге с нейросетью (я взял пока себе ник для учётки админа - Rector). . . .	Часы электронные Uhbif79 12.08.2026 Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .	Часы с будильником на основе класса QLCDNumber Uhbif79 12.08.2026 Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .	Установка MinGW GCC 16.2 и CMake 8Observer8 10.08.2026 VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия
Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо anaschu 10.08.2026 Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .	Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .	Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .

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

	По поводу рекурсии 29.07.2010, 04:58. Показов 4670. Ответов 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

Опции темы