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

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

Войти
Регистрация
Восстановить пароль
 
Doksim
57 / 57 / 8
Регистрация: 08.12.2013
Сообщений: 257
#1

В чем разница между Рекурсией и Итерацией? - C++

29.12.2013, 17:53. Просмотров 538. Ответов 13
Метки нет (Все метки)

Рекурсия позволяет сэкономить время но требует больше памяти, а циклы длятся дольше рекурсии но при этом занимают меньше памяти? Я правильно понимаю?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.12.2013, 17:53
Здравствуйте! Я подобрал для вас темы с ответами на вопрос В чем разница между Рекурсией и Итерацией? (C++):

В чем разница между С и С++ - C++
Возник вопрос в чем жи разница между С и С++ кроме того, что в С++ есть классы а в С их нету ?

В чем разница между [] и * ? - C++
Думал, что ни в чем, но когда попытался сделать так: (в файле 1) char lc; в файле 2: extern char* lc; Компилятор ругаться не стал,...

В чем разница между X x; и X x()? - C++
Корректный ли этот ответ?

В чем разница между new и malloc()? - C++
Всем доброго дня ! Начал читать книгу Пахомов Б. "C/C++ и MS Visual C++ 2008 для начинающих" До этого прочитал С++ за 21 день. ...

В чем разница между malloc и new? - C++
в чем разница? что лучше использовать?

В чем разница между const и constexpr? - C++
Когда стоит применять constexpr? В чём его отличие от const? Если можно конкретные примеры в их различиях. Например, constexpr int m =...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
outoftime
║XLR8║
510 / 432 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
29.12.2013, 17:59 #2
Абсолютно неправильно.

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

Рекурсии уступают по всем параметрам циклам кроме удобности и читаемости кода.
2
Байт
Эксперт C
16051 / 10320 / 1540
Регистрация: 24.12.2010
Сообщений: 19,438
29.12.2013, 18:07 #3
Цитата Сообщение от Doksim Посмотреть сообщение
Рекурсия позволяет сэкономить время но требует больше памяти, а циклы длятся дольше рекурсии но при этом занимают меньше памяти? Я правильно понимаю?
ИМХО, не совсем. Рекурсия и времени требует, как правило, больше (Накладные расходы на вызов функции).
Просто рекурсия красивше. И есть задачи, которые более осмысленно и понятно решаются с помощью рекурсии. Например, синтаксический разбор. Решать же задачи типа вычисления факториала или нахождения числа Фибонначи через рекурсию в серьезном практическом программировании - не советую. Там где можно свести к иттерации - сводите.
1
Doksim
57 / 57 / 8
Регистрация: 08.12.2013
Сообщений: 257
29.12.2013, 18:08  [ТС] #4
а зачем тогда придумали рекурсию?
0
Байт
Эксперт C
16051 / 10320 / 1540
Регистрация: 24.12.2010
Сообщений: 19,438
29.12.2013, 18:10 #5
Цитата Сообщение от Doksim Посмотреть сообщение
а зачем тогда придумали
Вопрос надо ставить шире. А зачем придумали программирование, колесо?...
0
Dmitriy_M
1349 / 1230 / 114
Регистрация: 20.03.2009
Сообщений: 4,420
Записей в блоге: 11
29.12.2013, 18:10 #6
Цитата Сообщение от Doksim Посмотреть сообщение
Я правильно понимаю?
Обязательно к прочтению
Структура и интерпретация компьютерных программ
Есть различные виды рекурсии, и некоторые из них современные компиляторы оптимизируют.
1
Doksim
57 / 57 / 8
Регистрация: 08.12.2013
Сообщений: 257
29.12.2013, 18:10  [ТС] #7
хм.. только что додумался проверить это - позасекать время. И рекурсия справляется быстрее
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
#include <iostream>
#include <ctime>
using namespace std;
 
int f( int i )
{
    if( i == 0 )return 0;
    cout << " " << i;
    return f( i - 1 );
}
 
int main()
 
{       
        const int n = 5;
        time_t start, end, start1, end1;
        
        start = clock();
        for( int i = 0; i < 100; i++ )
        f( n );
        end = clock();
        
        start1 = clock();
        for( int i = 0; i < 100; i++ )
        for( int j = n; j > 0; j--  )
        cout << " " << j;
        end1 = clock();
        
        cout << end - start << endl << end1 - start1;
        
        return system( "pause" );
        
}//---------------------------------------------------------------------------
0
outoftime
║XLR8║
510 / 432 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
29.12.2013, 18:13 #8
Цитата Сообщение от Байт Посмотреть сообщение
Просто рекурсия красивше. И есть задачи, которые более осмысленно и понятно решаются с помощью рекурсии. Например, синтаксический разбор.
Кроме того есть функциональные языки программирования, С++ считается итеративным языком программирования, но в текущее время он все больше и больше подхватывает фич именно функциональных языков, т.к. они обладают значительно вышей удобностью в написании и чтении\понимании кода.

Добавлено через 1 минуту
Цитата Сообщение от Doksim Посмотреть сообщение
for( int i = 0; i < 100; i++ )
Далеко не оптимальный вариант. Префиксная инкрементация работает быстрее. ++i
0
Dmitriy_M
1349 / 1230 / 114
Регистрация: 20.03.2009
Сообщений: 4,420
Записей в блоге: 11
29.12.2013, 18:22 #9
Цитата Сообщение от outoftime Посмотреть сообщение
Далеко не оптимальный вариант. Префиксная инкрементация работает быстрее. ++i
Ну не говори ерунды. Компиляторы давно это оптимизируют.
1
outoftime
║XLR8║
510 / 432 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
29.12.2013, 19:29 #10
Ладно, что-бы сравнять шансы запустим сначала итерацию, потом рекурсию и опять итерацию, замеряя только 4 точки. Далее будем замерять время выполнения элементраной вычислительной операции, что-бы убрать все посторонние факторы и запустим цикл на 10^7 вызовов.
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
40
41
42
#include <iostream>
#include <ctime>
 
#define EXPR(a) ((a)*(a) + (-a + 1) % (a) * a)
 
using namespace std;
 
void f( int i )
{
    if (i == 0) return;
    EXPR(i);
    f( i - 1 );
}
 
int main()
{
    const int n = 5, iterations = 10000000;
    time_t point[4];
 
    point[0] = clock();
 
    for( int i = 0, j; i < iterations; ++i )
        for( j = n; j; --j )
            EXPR(j);
 
    point[1] = clock();
 
    for( int i = 0; i < iterations; ++i )
        f( n );
 
    point[2] = clock();
 
    for( int i = 0, j; i < iterations; ++i )
        for( j = n; j; --j )
            EXPR(j);
 
    point[3] = clock();
 
    //cout << end - start << endl << end1 - start1;
    for (int i = 0; i < 3; ++i)
        std::cout << point[i+1] - point[i] << std::endl;
}
Bash
1
2
3
227
317
192
Добавлено через 16 минут
Вот еще один пример с раскручиваемой хвостовой рекурсией:
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
40
#include <cstdio>
#include <ctime>
 
#define EXPR(a) ((a)*(a) + (-a + 1) % (a) * a)
 
using namespace std;
 
void f( int i )
{
    if (i == 0) return;
    EXPR(i);
    f( i - 1 );
}
 
int main()
{
    const int n = 5, iterations = 1e7;
    time_t point[2] = {0};
 
    for (int i = 0; i < 20; ++i)
    {
        if (i & 1)
        {
            point[1] = clock();
            printf("recursion: %d\n", point[1] - point[0]);
 
            for (int a(0), b; a < iterations; ++a)
                for (b = n; b != 0; --b)
                    EXPR(b);
        }
        else
        {
            point[0] = clock();
            printf("iteration: %d\n", point[0] - point[1]);
 
            for (int a(0), b; a < iterations; ++a)
                f(n);
        }
    }
}
Bash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
iteration: 4
recursion: 346
iteration: 217
recursion: 348
iteration: 211
recursion: 348
iteration: 216
recursion: 345
iteration: 220
recursion: 346
iteration: 221
recursion: 346
iteration: 216
recursion: 346
iteration: 223
recursion: 344
iteration: 223
recursion: 346
iteration: 219
recursion: 345
Сейчас попробую написать рекурсию которую компилятор не сможет раскрутить.

Добавлено через 22 минуты
Погуглил инфу о хвостовых рекурсиях, такая рекурсия считается хвостовой (т.к. компилятор может раскрутить только хвостовою рекурсию, которая после оптимизаций не будет использовать стек) и запутался (:

Момент с задержками на вызов функции я показал. Есть еще момент с ограничением стека, но люди его обходят использую опять таких именно хвостовые рекурсии.
2
Doksim
57 / 57 / 8
Регистрация: 08.12.2013
Сообщений: 257
29.12.2013, 20:10  [ТС] #11
Цитата Сообщение от outoftime Посмотреть сообщение
Далеко не оптимальный вариант. Префиксная инкрементация работает быстрее. ++i
первый раз слышу, даже если так, то насколько быстрее? наверняка меньше одной милисек. но понимать префиксную инкрментацию сложнее
0
Tulosba
:)
Эксперт С++
4395 / 3238 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
29.12.2013, 20:16 #12
Цитата Сообщение от outoftime Посмотреть сообщение
Префиксная инкрементация работает быстрее. ++i
Для простых типов (например, int) никакой разницы в упомянутом цикле не будет. Для сравнение - посмотрите на ассемблерный выхлоп.
А вот если используется какой-то сложный класс итератора, то использовании постфиксной формы инкремента повлечет за собой создание временного объекта.
2
Dmitriy_M
1349 / 1230 / 114
Регистрация: 20.03.2009
Сообщений: 4,420
Записей в блоге: 11
30.12.2013, 10:13 #13
Цитата Сообщение от Tulosba Посмотреть сообщение
А вот если используется какой-то сложный класс итератора, то использовании постфиксной формы инкремента повлечет за собой создание временного объекта.
У
Герба Саттера в "Решение сложных задач на С++" есть ремарка по оптимизации инкремента компилятором. При некоторых условиях компилятор может и итератор оптимизировать.
0
Tulosba
30.12.2013, 11:32     В чем разница между Рекурсией и Итерацией?
  #14

Не по теме:

Цитата Сообщение от Dmitriy_M Посмотреть сообщение
есть ремарка по оптимизации инкремента компилятором.
Лучше бы ссылочку на страницу или скан.

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.12.2013, 11:32
Привет! Вот еще темы с ответами:

В чем разница между вектором и массивом - C++
Я учу язык С/С++ и хотел у вас спросить в чем разница между вектором и массивом ? кроме тогдо что вектор создается vector&lt;int&gt; m; а массив...

В чем разница между random и randomize? - C++
в чем разница между random и randomize??

В чем разница между Double и Float? - C++
Хмм? :(

В чем разница между push_back и push? - C++
Подскажите пожалуйста, в чем состоит отличие Push_back и просто Push? Они оба насколько я знаю добавляют значение в конец, но например у...


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

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

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