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

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

Восстановить пароль Регистрация
 
Doksim
 Аватар для Doksim
57 / 57 / 8
Регистрация: 08.12.2013
Сообщений: 257
29.12.2013, 17:53     В чем разница между Рекурсией и Итерацией? #1
Рекурсия позволяет сэкономить время но требует больше памяти, а циклы длятся дольше рекурсии но при этом занимают меньше памяти? Я правильно понимаю?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.12.2013, 17:53     В чем разница между Рекурсией и Итерацией?
Посмотрите здесь:

В чем разница между вектором и массивом C++
C++ В чем разница между push_back и push?
C++ В чем разница между инициализацией и присваиванием?
C++ В чем разница между new и malloc()?
В чем разница между scanf_s и scanf? C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
29.12.2013, 17:59     В чем разница между Рекурсией и Итерацией? #2
Абсолютно неправильно.

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

Рекурсии уступают по всем параметрам циклам кроме удобности и читаемости кода.
Байт
 Аватар для Байт
13970 / 8801 / 1226
Регистрация: 24.12.2010
Сообщений: 15,944
29.12.2013, 18:07     В чем разница между Рекурсией и Итерацией? #3
Цитата Сообщение от Doksim Посмотреть сообщение
Рекурсия позволяет сэкономить время но требует больше памяти, а циклы длятся дольше рекурсии но при этом занимают меньше памяти? Я правильно понимаю?
ИМХО, не совсем. Рекурсия и времени требует, как правило, больше (Накладные расходы на вызов функции).
Просто рекурсия красивше. И есть задачи, которые более осмысленно и понятно решаются с помощью рекурсии. Например, синтаксический разбор. Решать же задачи типа вычисления факториала или нахождения числа Фибонначи через рекурсию в серьезном практическом программировании - не советую. Там где можно свести к иттерации - сводите.
Doksim
 Аватар для Doksim
57 / 57 / 8
Регистрация: 08.12.2013
Сообщений: 257
29.12.2013, 18:08  [ТС]     В чем разница между Рекурсией и Итерацией? #4
а зачем тогда придумали рекурсию?
Байт
 Аватар для Байт
13970 / 8801 / 1226
Регистрация: 24.12.2010
Сообщений: 15,944
29.12.2013, 18:10     В чем разница между Рекурсией и Итерацией? #5
Цитата Сообщение от Doksim Посмотреть сообщение
а зачем тогда придумали
Вопрос надо ставить шире. А зачем придумали программирование, колесо?...
Dmitriy_M
1294 / 1175 / 104
Регистрация: 20.03.2009
Сообщений: 4,208
Записей в блоге: 11
29.12.2013, 18:10     В чем разница между Рекурсией и Итерацией? #6
Цитата Сообщение от Doksim Посмотреть сообщение
Я правильно понимаю?
Обязательно к прочтению
Структура и интерпретация компьютерных программ
Есть различные виды рекурсии, и некоторые из них современные компиляторы оптимизируют.
Doksim
 Аватар для 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" );
        
}//---------------------------------------------------------------------------
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
29.12.2013, 18:13     В чем разница между Рекурсией и Итерацией? #8
Цитата Сообщение от Байт Посмотреть сообщение
Просто рекурсия красивше. И есть задачи, которые более осмысленно и понятно решаются с помощью рекурсии. Например, синтаксический разбор.
Кроме того есть функциональные языки программирования, С++ считается итеративным языком программирования, но в текущее время он все больше и больше подхватывает фич именно функциональных языков, т.к. они обладают значительно вышей удобностью в написании и чтении\понимании кода.

Добавлено через 1 минуту
Цитата Сообщение от Doksim Посмотреть сообщение
for( int i = 0; i < 100; i++ )
Далеко не оптимальный вариант. Префиксная инкрементация работает быстрее. ++i
Dmitriy_M
1294 / 1175 / 104
Регистрация: 20.03.2009
Сообщений: 4,208
Записей в блоге: 11
29.12.2013, 18:22     В чем разница между Рекурсией и Итерацией? #9
Цитата Сообщение от outoftime Посмотреть сообщение
Далеко не оптимальный вариант. Префиксная инкрементация работает быстрее. ++i
Ну не говори ерунды. Компиляторы давно это оптимизируют.
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
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 минуты
Погуглил инфу о хвостовых рекурсиях, такая рекурсия считается хвостовой (т.к. компилятор может раскрутить только хвостовою рекурсию, которая после оптимизаций не будет использовать стек) и запутался (:

Момент с задержками на вызов функции я показал. Есть еще момент с ограничением стека, но люди его обходят использую опять таких именно хвостовые рекурсии.
Doksim
 Аватар для Doksim
57 / 57 / 8
Регистрация: 08.12.2013
Сообщений: 257
29.12.2013, 20:10  [ТС]     В чем разница между Рекурсией и Итерацией? #11
Цитата Сообщение от outoftime Посмотреть сообщение
Далеко не оптимальный вариант. Префиксная инкрементация работает быстрее. ++i
первый раз слышу, даже если так, то насколько быстрее? наверняка меньше одной милисек. но понимать префиксную инкрментацию сложнее
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
29.12.2013, 20:16     В чем разница между Рекурсией и Итерацией? #12
Цитата Сообщение от outoftime Посмотреть сообщение
Префиксная инкрементация работает быстрее. ++i
Для простых типов (например, int) никакой разницы в упомянутом цикле не будет. Для сравнение - посмотрите на ассемблерный выхлоп.
А вот если используется какой-то сложный класс итератора, то использовании постфиксной формы инкремента повлечет за собой создание временного объекта.
Dmitriy_M
1294 / 1175 / 104
Регистрация: 20.03.2009
Сообщений: 4,208
Записей в блоге: 11
30.12.2013, 10:13     В чем разница между Рекурсией и Итерацией? #13
Цитата Сообщение от Tulosba Посмотреть сообщение
А вот если используется какой-то сложный класс итератора, то использовании постфиксной формы инкремента повлечет за собой создание временного объекта.
У
Герба Саттера в "Решение сложных задач на С++" есть ремарка по оптимизации инкремента компилятором. При некоторых условиях компилятор может и итератор оптимизировать.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.12.2013, 11:32     В чем разница между Рекурсией и Итерацией?
Еще ссылки по теме:

В чем разница между malloc и new? C++
В чем разница между Double и Float? C++
C++ В чем разница между Debug and Release?

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

Или воспользуйтесь поиском по форуму:
Tulosba
30.12.2013, 11:32     В чем разница между Рекурсией и Итерацией?
  #14

Не по теме:

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

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

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