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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Удалить числительное из строки, вводимое самим человеком, а не заранее подготовленный текст http://www.cyberforum.ru/cpp-beginners/thread1060166.html
Всем здравствуйте!!! Очень нужна ваша помощь, а именно нужно удалить числительное из строки, вводимое самим человеком, а не заранее подготовленный текст. Например самому ввести: "Twenty one century", а на выходе получить просто century. Заранее благодарен. Просто очень срочно!!!
C++ какие преимущества дает интерфейсное программирование? Дорогие программисты, во первых, хочу поздравить вас с Наступающим новым Годом! Я к вам обращаюсь с маленькой просьбой. Я никак не могу ответить на оставшиеся 5 вопросов из лабораторной,которые состоят из 25 вопросов!(На другие 20 я ответил,на эти прост не могу вдуплить,че да как),вот вопросы: 1)какие преимущества дает интерфейсное программирование( с использованием обстрактных базовых классов)... http://www.cyberforum.ru/cpp-beginners/thread1060160.html
аналог input().split() C++ C++
Здравствуйте. Вопрос такой: вводится строка. надо подстроки (по пробелам) занести в vector<string> Как это сделать?
Подскажите пожалуйста C++
Как в блок-схеме описываются эти две строчки? for (map<std::string,int>::iterator p = count.begin(); p != count.end(); p++) cout << p->first<<'\t'<<p->second<<'\n';
C++ Не получается каждый байт переменной вывести побитно http://www.cyberforum.ru/cpp-beginners/thread1060136.html
Здравствуйте. С помощью шаблонов, нужно разный тип переменной разбить на байты и каждый байт вывести по битам. . Насчет побитно разложить и вычислить сколько байт в переменной понятно как. Надо как то каждый байт переменной загнать в массив char и потом каждый элемент прогонять через функци. преобразования в биты (printbyte(p). Плохо понял эту тему с преобразовыванием и шаблонами, может...
C++ Параметры не передаются в конструктор класса Всем привет, у меня такая проблема. Параметры не передаются в конструктор класса. Telem *c; try{ c = new Telem(st, f, 1.1); } catch(std::exception& e){ std::cout << "exception caught: " << e.what() << endl; } подробнее

Показать сообщение отдельно
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
29.12.2013, 19:29     В чем разница между Рекурсией и Итерацией?
Ладно, что-бы сравнять шансы запустим сначала итерацию, потом рекурсию и опять итерацию, замеряя только 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 минуты
Погуглил инфу о хвостовых рекурсиях, такая рекурсия считается хвостовой (т.к. компилятор может раскрутить только хвостовою рекурсию, которая после оптимизаций не будет использовать стек) и запутался (:

Момент с задержками на вызов функции я показал. Есть еще момент с ограничением стека, но люди его обходят использую опять таких именно хвостовые рекурсии.
 
Текущее время: 13:28. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru