Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.85/13: Рейтинг темы: голосов - 13, средняя оценка - 4.85
57 / 57 / 10
Регистрация: 08.12.2013
Сообщений: 257
1

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

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

Рекурсия позволяет сэкономить время но требует больше памяти, а циклы длятся дольше рекурсии но при этом занимают меньше памяти? Я правильно понимаю?
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
29.12.2013, 17:53
Ответы с готовыми решениями:

Пояснить разницу между рекурсией и итерацией на примере
Всем привет, можете объяснить разницу между рекурсией и итерацией. С помощью примера пожалуйста.

Объясните, пожалуйста, чайнику разницу между рекурсией, корекурсией и итерацией
Уважаемые знатоки, Объясните, пожалуйста, несведущему разницу между рекурсией, корекурсией и...

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

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

13
║XLR8║
1212 / 909 / 270
Регистрация: 25.07.2009
Сообщений: 4,361
Записей в блоге: 5
29.12.2013, 17:59 2
Абсолютно неправильно.

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

Рекурсии уступают по всем параметрам циклам кроме удобности и читаемости кода.
2
Диссидент
Эксперт C
26614 / 16562 / 3621
Регистрация: 24.12.2010
Сообщений: 36,950
29.12.2013, 18:07 3
Цитата Сообщение от Doksim Посмотреть сообщение
Рекурсия позволяет сэкономить время но требует больше памяти, а циклы длятся дольше рекурсии но при этом занимают меньше памяти? Я правильно понимаю?
ИМХО, не совсем. Рекурсия и времени требует, как правило, больше (Накладные расходы на вызов функции).
Просто рекурсия красивше. И есть задачи, которые более осмысленно и понятно решаются с помощью рекурсии. Например, синтаксический разбор. Решать же задачи типа вычисления факториала или нахождения числа Фибонначи через рекурсию в серьезном практическом программировании - не советую. Там где можно свести к иттерации - сводите.
1
57 / 57 / 10
Регистрация: 08.12.2013
Сообщений: 257
29.12.2013, 18:08  [ТС] 4
а зачем тогда придумали рекурсию?
0
Диссидент
Эксперт C
26614 / 16562 / 3621
Регистрация: 24.12.2010
Сообщений: 36,950
29.12.2013, 18:10 5
Цитата Сообщение от Doksim Посмотреть сообщение
а зачем тогда придумали
Вопрос надо ставить шире. А зачем придумали программирование, колесо?...
0
1441 / 1322 / 131
Регистрация: 20.03.2009
Сообщений: 4,689
Записей в блоге: 11
29.12.2013, 18:10 6
Цитата Сообщение от Doksim Посмотреть сообщение
Я правильно понимаю?
Обязательно к прочтению
Структура и интерпретация компьютерных программ
Есть различные виды рекурсии, и некоторые из них современные компиляторы оптимизируют.
1
57 / 57 / 10
Регистрация: 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
║XLR8║
1212 / 909 / 270
Регистрация: 25.07.2009
Сообщений: 4,361
Записей в блоге: 5
29.12.2013, 18:13 8
Цитата Сообщение от Байт Посмотреть сообщение
Просто рекурсия красивше. И есть задачи, которые более осмысленно и понятно решаются с помощью рекурсии. Например, синтаксический разбор.
Кроме того есть функциональные языки программирования, С++ считается итеративным языком программирования, но в текущее время он все больше и больше подхватывает фич именно функциональных языков, т.к. они обладают значительно вышей удобностью в написании и чтении\понимании кода.

Добавлено через 1 минуту
Цитата Сообщение от Doksim Посмотреть сообщение
for( int i = 0; i < 100; i++ )
Далеко не оптимальный вариант. Префиксная инкрементация работает быстрее. ++i
0
1441 / 1322 / 131
Регистрация: 20.03.2009
Сообщений: 4,689
Записей в блоге: 11
29.12.2013, 18:22 9
Цитата Сообщение от outoftime Посмотреть сообщение
Далеко не оптимальный вариант. Префиксная инкрементация работает быстрее. ++i
Ну не говори ерунды. Компиляторы давно это оптимизируют.
1
║XLR8║
1212 / 909 / 270
Регистрация: 25.07.2009
Сообщений: 4,361
Записей в блоге: 5
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
57 / 57 / 10
Регистрация: 08.12.2013
Сообщений: 257
29.12.2013, 20:10  [ТС] 11
Цитата Сообщение от outoftime Посмотреть сообщение
Далеко не оптимальный вариант. Префиксная инкрементация работает быстрее. ++i
первый раз слышу, даже если так, то насколько быстрее? наверняка меньше одной милисек. но понимать префиксную инкрментацию сложнее
0
:)
Эксперт С++
4771 / 3265 / 497
Регистрация: 19.02.2013
Сообщений: 9,046
29.12.2013, 20:16 12
Цитата Сообщение от outoftime Посмотреть сообщение
Префиксная инкрементация работает быстрее. ++i
Для простых типов (например, int) никакой разницы в упомянутом цикле не будет. Для сравнение - посмотрите на ассемблерный выхлоп.
А вот если используется какой-то сложный класс итератора, то использовании постфиксной формы инкремента повлечет за собой создание временного объекта.
2
1441 / 1322 / 131
Регистрация: 20.03.2009
Сообщений: 4,689
Записей в блоге: 11
30.12.2013, 10:13 13
Цитата Сообщение от Tulosba Посмотреть сообщение
А вот если используется какой-то сложный класс итератора, то использовании постфиксной формы инкремента повлечет за собой создание временного объекта.
У
Герба Саттера в "Решение сложных задач на С++" есть ремарка по оптимизации инкремента компилятором. При некоторых условиях компилятор может и итератор оптимизировать.
0
Tulosba
30.12.2013, 11:32     В чем разница между Рекурсией и Итерацией?
  #14

Не по теме:

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

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
30.12.2013, 11:32

В чем разница между ^p и ^13
Заменой сделал строку с ^p и строку с ^13 с Подстановочными знаками. Если поместить курсор на...

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

В чем разница между \n и \r
Здравствуйте. Собственно вопрос в название темы. Объясните, в чем разница между /n и /r?

В чем разница между С++ и С?
Чем отличается С и С++, кроме того что С++ есть ООП?

В чем разница между . и ,
Вот столкнулся с таким вопросом вчем разница между . и , Привер &lt;? echo...

В чём разница между .each() и $.each()
читаю про jquery и там есть .each() и $.each() в чем разница? Где можно прочитать про тонкости...


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

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru