Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Для новичков > вопрос о рекурсивных функциях

Автор: fedorizprostokvashino 16.1.2009, 12:11

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

Код


#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

рекурсивная

Автор: pan2004 16.1.2009, 12:24

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

)

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

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

Автор: fedorizprostokvashino 16.1.2009, 12:30

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

Автор: pan2004 16.1.2009, 12:32

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

)

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

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

Автор: fedorizprostokvashino 16.1.2009, 12:34

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

Автор: pan2004 16.1.2009, 12:36

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

Код


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

Автор: fedorizprostokvashino 16.1.2009, 12:41

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

Код


#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

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

)

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

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

Автор: Lazin 16.1.2009, 12:45

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

)

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

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

Автор: mes 16.1.2009, 12:45

Цитата(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 << " ";

}

Автор: fedorizprostokvashino 16.1.2009, 12:56

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

Автор: mes 16.1.2009, 12:59

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

)

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

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

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

)

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

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

Автор: fedorizprostokvashino 16.1.2009, 13:01

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

Автор: mes 16.1.2009, 13:08

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

)

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

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

Автор: fedorizprostokvashino 16.1.2009, 13:18

ну и наверно можно (а может быть и нужно) использовать глобальные переменные

Автор: mes 16.1.2009, 13:20

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

)

ну и наверно можно (а может быть и нужно) использовать глобальные переменные

старайтесь оставить эту возможность, только на случай крайней необходимости.. Если получится - избежите многих проблем smile

Автор: fedorizprostokvashino 16.1.2009, 13:24

точно

но мы будем аккуратно smile