VPF::вопрос о рекурсивных функциях

fedorizprostokvashino

Дата 16.1.2009, 12:11 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 8
Регистрация: 16.1.2009

Репутация: нет
Всего: нет

Здрасти, вопросик мона задать

Код


#include <iostream>

using namespace std;

void func(int x = 0){
    x++;

    cout << x << " ";

    if (x < 20)
        func(x);
    else
       return;
}

int main(){
    func();

    return 0;
}

func - это рекурсивная функция или нет?

Lazin

Дата 16.1.2009, 12:20 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3820
Регистрация: 11.12.2006
Где: paranoid oil empi re

Репутация: 27
Всего: 154

рекурсивная

--------------------

C++ is the steampunk of programming languages: modern ideas realized with victorian technology.

pan2004

Дата 16.1.2009, 12:24 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 357
Регистрация: 28.7.2007

Репутация: 2
Всего: 9

Цитата(fedorizprostokvashino @ 16.1.2009, 12:11

)

func - это рекурсивная функция или нет?

она вызывает саму себя(пусть даже и не во всех случаях), значит рекурсивная.

--------------------

Qt4/C++ fan
WinXP SP3: MSVC++2005 Qt4.5.1 Boost1.39
сыграем в дурака?

fedorizprostokvashino

Дата 16.1.2009, 12:30 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 8
Регистрация: 16.1.2009

Репутация: нет
Всего: нет

насколько я погимаю то в маём случае до конца выполнения программы будет создано 20 копий функций func и все они в момент выполнения программы будут висеть в оперативной памяти. А как бы переписать эту функцию чтоб предыдущая "умирала" а текущая работала, чтоб памяти сэкономить.

pan2004

Дата 16.1.2009, 12:32 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 357
Регистрация: 28.7.2007

Репутация: 2
Всего: 9

Цитата(fedorizprostokvashino @ 16.1.2009, 12:30

)

до конца выполнения программы будет создано 20 копий функций func

Никаких "копий" функции не создается, просто при вызове функции в стеке запоминается обратный адрес. Он занимает всего 4 байта(по крайней мере на x32), так что много памяти ты не сэкономишь)

--------------------

Qt4/C++ fan
WinXP SP3: MSVC++2005 Qt4.5.1 Boost1.39
сыграем в дурака?

fedorizprostokvashino

Дата 16.1.2009, 12:34 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 8
Регистрация: 16.1.2009

Репутация: нет
Всего: нет

спасибо добрый человек разяснил smile

pan2004

Дата 16.1.2009, 12:36 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 357
Регистрация: 28.7.2007

Репутация: 2
Всего: 9

а переписать можно так

Код


for (int a = 0; a < 20; ++a)
   std::cout << a << " ";

--------------------

Qt4/C++ fan
WinXP SP3: MSVC++2005 Qt4.5.1 Boost1.39
сыграем в дурака?

fedorizprostokvashino

Дата 16.1.2009, 12:41 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 8
Регистрация: 16.1.2009

Репутация: нет
Всего: нет

канеш мона, просто я рекурсию плохо знаю. Привык код рекурсии видеть типа:

Код


#include <iostream>

using namespace std;

void func(int x = 0){
    x++;

    cout << x << " ";

    if (x < 20)
        return func(x);
    else
       return;
}

int main(){
    func();

    return 0;
}

вот я и думаю в чем разница. Ну всмысле вызов самой себя ставят после слова return

pan2004

Дата 16.1.2009, 12:44 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 357
Регистрация: 28.7.2007

Репутация: 2
Всего: 9

Цитата(fedorizprostokvashino @ 16.1.2009, 12:41

)

вот я и думаю в чем разница. Ну всмысле вызов самой себя ставят после слова return

в данном случае в этом мало смысла, тк функция возвращает void, те ничего)

--------------------

Qt4/C++ fan
WinXP SP3: MSVC++2005 Qt4.5.1 Boost1.39
сыграем в дурака?

Lazin

Дата 16.1.2009, 12:45 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3820
Регистрация: 11.12.2006
Где: paranoid oil empi re

Репутация: 27
Всего: 154

Цитата(fedorizprostokvashino @ 16.1.2009, 12:30

)

насколько я погимаю то в маём случае до конца выполнения программы будет создано 20 копий функций func и все они в момент выполнения программы будут висеть в оперативной памяти.

это не так, ф-я только одна, но она вызывается 20 раз

--------------------

C++ is the steampunk of programming languages: modern ideas realized with victorian technology.

mes

Дата 16.1.2009, 12:45 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250

Цитата(pan2004 @ 16.1.2009, 11:32

)

. Он занимает всего 4 байта(по крайней мере на x32)

также стек помещаются аргументы и локальные переменные - для каждой функции свои.

Цитата(fedorizprostokvashino @ 16.1.2009, 11:30

)

А как бы переписать эту функцию чтоб предыдущая "умирала" а текущая работала, чтоб памяти сэкономить.

В принципе весь вопрос только в глубине вызовов . Если рекурсия непозволительна, то во многих случаях ее можно заменить циклом

Цитата(fedorizprostokvashino @ 16.1.2009, 11:11

)

void func(int x = 0){
    x++;
    cout << x << " ";
    if (x < 20)
        func(x);
    else
       return;
}

например так :

Код


void func(int x = 0){
do  {    cout << ++x << " "; }    while (x < 20);
}

или так :

Код


void func(int x = 0){
for (; x<20;)  cout << ++x << " ";

}

--------------------

http://opendots.net

fedorizprostokvashino

Дата 16.1.2009, 12:56 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 8
Регистрация: 16.1.2009

Репутация: нет
Всего: нет

болшое спсб за разяснения. про цикл можно было и не говорить и так понятно что в этном случае его и надо использовать. просто я думаю что первый вызов func не завиршился, а значит перемменые в этой функции находятся в памяти, затем запускается вторая такая же функция (ее копия) но уже со своими значениями переменных (которые эстественно опять попадают в память) и тд (те 20раз). А после выполнения последнего раза память освобождается всеми этими переменными которые оброзовались.

mes

Дата 16.1.2009, 12:59 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250

Цитата(fedorizprostokvashino @ 16.1.2009, 11:56

)

просто я думаю что первый вызов func не завиршился, а значит перемменые в этой функции находятся в памяти, затем запускается вторая такая же функция (ее копия) но уже со своими значениями переменных (которые эстественно опять попадают в память) и тд (те 20раз)

ага, каждый раз стек забивается

Цитата(fedorizprostokvashino @ 16.1.2009, 11:56

)

А после выполнения последнего раза память освобождается всеми этими переменными которые оброзовались.

не совсем так. Стек начинает раскручиваться в обратном порядке :
Вначале освободится память занимаемая 20й функцией, потом 19 и так далее.

--------------------

http://opendots.net

fedorizprostokvashino

Дата 16.1.2009, 13:01 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 8
Регистрация: 16.1.2009

Репутация: нет
Всего: нет

во терь мы поняли друг друга. мне просто принцип интересен и экономия от него.

mes

Дата 16.1.2009, 13:08 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250

Цитата(fedorizprostokvashino @ 16.1.2009, 12:01

)

мне просто принцип интересен и экономия от него.

как следует из вышесказанного в рекурсии не желательно создавать большое кол-во локальных перемен,
все что ненужно выносится за пределы функции (например в другие вспомогательные функции), тогда они не будут загромаждать стек.

--------------------

http://opendots.net

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »