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

Рекурсивная функция - C++

Восстановить пароль Регистрация
 
BAIZOR
0 / 0 / 0
Регистрация: 30.10.2010
Сообщений: 68
06.01.2011, 06:54     Рекурсивная функция #1
Как быть?

Мне надо вызывать рекурсивную функцию очень много раз,вплоть до того что вылетает ошибка unhandled exception at ... 0xC00000FD stack overflow

Но я не вижу другого решения своей задачи,как не рекурсия...
Я надеюсь есть какие то способы вызывать рекурсию ужасное кол-во раз (10000++++) ?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.01.2011, 06:54     Рекурсивная функция
Посмотрите здесь:

Рекурсивная функция C++
C++ рекурсивная функция
C++ рекурсивная функция
Рекурсивная функция C++
Рекурсивная функция C++ C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
KEKCoGEN
Модератор
 Аватар для KEKCoGEN
1711 / 1589 / 386
Регистрация: 28.12.2010
Сообщений: 6,485
06.01.2011, 07:00     Рекурсивная функция #2
Впринципе можно увеличить стек, но наверняка можно оптимизировать алгоритм. Может приведете код рекурсии?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
06.01.2011, 09:27     Рекурсивная функция #3
BAIZOR, условие задачи напишите и код который Вы написали.
BAIZOR
0 / 0 / 0
Регистрация: 30.10.2010
Сообщений: 68
06.01.2011, 14:43  [ТС]     Рекурсивная функция #4
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
int* Lab1_All_Perebor(int **A,int *n,int *indexes,int *bestN,int *bestIndexes,int *bestShtraf,int *bestPrice,int *price,bool *metod)
{
    
    //Sleep(10);
    p++;
    SendMessage(GhWnd,WM_COLORED,(WPARAM)*n,(LPARAM)indexes);
    if(*n>N)
    {
        if(*bestN>0)
        {
            int *timebuf;timebuf=new int[*bestN+1];
            timebuf[0]=*bestN;
            for(int q=1;q<*bestN+1;q++)
            {
                timebuf[q]=bestIndexes[q-1];
            }
            return timebuf;//////////////////////////////////////////EXIT
        }
        else
        {
            int *timebuf;timebuf=new int[1];timebuf[0]=0;
            return timebuf;//////////////////////////////////////////EXIT
        }
    }
    int *buf;
    buf=new int[M-1];
    for(int q=0;q<M-1;q++)
    {
        buf[q]=0;
    }
    int thisShtraf=0;
    *price=0;
    for(int Q=0;Q<*n;Q++)
    {
        for(int q=0;q<M-1;q++)
        {
            buf[q]+=A[indexes[Q]][q];
        }
        *price+=A[indexes[Q]][M-1];
    }
    bool flag=true;
    for(int q=0;q<M-1;q++)
    {
        if(buf[q]>1){thisShtraf++;}
        if(buf[q]==0){flag=false;}
    }
    delete buf;
 
    if(*metod)
    {
        if(flag&&thisShtraf<*bestShtraf)
        {
            flag=false;
            *bestShtraf=thisShtraf;
            *bestN=*n;
            //delete bestIndexes;
            bestIndexes=new int[*n];
            *bestPrice=*price;
            for(int q=0;q<*n;q++)
            {
                bestIndexes[q]=indexes[q];
            }
        }
    }
    else
    {
        if(flag&&*price<*bestPrice)
        {
            flag=false;
            *bestShtraf=thisShtraf;
            *bestN=*n;
            //delete bestIndexes;
            bestIndexes=new int[*n];
            *bestPrice=*price;
            for(int q=0;q<*n;q++)
            {
                bestIndexes[q]=indexes[q];
            }
        }
    }
    
 
    /////////////////////////////////////////////////////SHOW
 
    ////system("cls");
    ////wcout<<L"\n\n   Это "<<p<<L" проход функции\n\n\n\n";
    //for(int q=0;q<n;q++)
    //{
    //  //cout<<"                  ";
    //  for(int w=0;w<M;w++)
    //  {
    //      //cout<<A[indexes[q]][w]<<"  ";
    //  }
    //  //cout<<"          "<<indexes[q]<<endl;
    //}
    ////wcout<<"\n\n\n       buf        ";for(int q=0;q<M;q++){cout<<buf[q]<<"  ";}cout<<"\n\n\n";
    //if(bestN>0)
    //{
    //  //wcout<<L"                              Лучший:\n";
    //  for(int q=0;q<bestN;q++)
    //  {
    //      //cout<<"                  ";
    //      for(int w=0;w<M;w++)
    //      {
    //          //cout<<A[bestIndexes[q]][w]<<"  ";
    //      }
    //      //cout<<"          "<<bestIndexes[q]<<endl;
    //  }
    //}
    ////getch();///////////////////////WAIT BUTTON
 
    ///////////////////////////////////////////////////////////
 
    if(indexes[*n-1]<N-1)
    {
        indexes[*n-1]++;
        return Lab1_All_Perebor(A,n,indexes,bestN,bestIndexes,bestShtraf,bestPrice,price,metod);////////RECYRTION
    }
    else
    {
        if(*n==1)
        {
            if(indexes[0]<N-1)
            {
                indexes[0]++;
            }
            else
            {
                *n+=1;
                //delete indexes;
                indexes=new int[*n];
                for(int q=0;q<*n;q++)
                {
                    indexes[q]=q;
                }
            }
            return Lab1_All_Perebor(A,n,indexes,bestN,bestIndexes,bestShtraf,bestPrice,price,metod);////////RECYRTION
        }
 
        for(int q=*n-1;q>=0;q--)
        {
            if(indexes[q]<indexes[q+1]-1){indexes[q]++;for(int w=q+1;w<*n;w++){indexes[w]=indexes[w-1]+1;}
                return Lab1_All_Perebor(A,n,indexes,bestN,bestIndexes,bestShtraf,bestPrice,price,metod);////////RECYRTION
            }
            if(q==0)
            {
                *n+=1;
                //delete indexes;
                indexes=new int[*n];
                for(int q=0;q<*n;q++)
                {
                    indexes[q]=q;
                }
                return Lab1_All_Perebor(A,n,indexes,bestN,bestIndexes,bestShtraf,bestPrice,price,metod);////////RECYRTION
            }
        }
        
        *n+=1;
        //delete indexes;
        indexes=new int[*n];
        for(int q=0;q<*n;q++)
        {
            indexes[q]=q;
        }
        
        ////
        return Lab1_All_Perebor(A,n,indexes,bestN,bestIndexes,bestShtraf,bestPrice,price,metod);////////RECYRTION
    }
}
Имеем матрицу из 0 и 1 (**A)
Функция должна вернуть массив индексов лучшего варианта слияния строк...
Строки сливаются или по найлучшему штрафу (когда при их сумирование образуется строка из только единиц,любой элемент который больше 1 добавляется к штрафу-1) если metod=true.
Или по найменьшей цене (сумма последних элементов сумируемых строк) если metod=false.

Впринципе я вижу решение если сделать вместо всех return поставить continue и сделать не рекурсию а вечный цикл используя проверку на выход из цыкла от рекурсии.
Останеться сделать только все переменные за этим цыклом.

Но мне интересно возможно ли сделать так что бы рекурсия вызывалась очень много раз ?
dikanev
21 / 21 / 1
Регистрация: 28.05.2010
Сообщений: 67
06.01.2011, 14:45     Рекурсивная функция #5
Стек можно использовать явно, тогда никаких ограничений не будет. Рекурсия подразумевает, что решение задачи требует решения подобных подзадач, отличающихся набором параметров. Что надо делать в каждой подзадаче определяется набором параметров. Так вот вместо рекурсивных вызовов надо помещать параметры текущей подзадачи в стек и заниматься решением верхней в стеке подзадачи пока стек не опустеет.

Наверное, проще будет понять на примере. Вместо
Delphi
1
2
3
4
5
6
7
8
9
10
11
procedure RecProc(параметры1);
begin
  DoSomething(параметры1);
  if <условие> then
  begin
    параметры2 := f(параметры1);
    RecProc(параметры2);
    параметры3 := g(параметры1);
    RecProc(параметры3);
  end;
end;
следует писать
Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
procedure NonRecProc(параметры1);
begin
  PushStack(параметры1); //Помещаем параметры1 в стек
  while <стэк не пуст> do
  begin
    пареметры := PopStack; //достаем параметры из стека
    DoSomething(параметры);
    if <условие> then
    begin
      параметры3 := f(параметры);
      PushStack(параметры3);
      параметры2 := f(параметры);
      PushStack(параметры2);
    end;
  end;
end;
Upd. Не посмотрел, что это сишный форум. Но думаю идея понятна и на Паскале.
BAIZOR
0 / 0 / 0
Регистрация: 30.10.2010
Сообщений: 68
06.01.2011, 14:51  [ТС]     Рекурсивная функция #6
Размер матрицы NxM
n это кол-во строк для склеивания(суммирования)

dikanev,а вы бы не могли привести пример на Visual С++?
dikanev
21 / 21 / 1
Регистрация: 28.05.2010
Сообщений: 67
06.01.2011, 15:17     Рекурсивная функция #7
То же на C++
C++
1
2
3
4
5
6
7
8
9
void RecFunc(параметры1){
  DoSomething(параметры1);
  if (условие) {
    параметры2 = f(параметры1);
    RecFunc(параметры2);
    параметры3 = g(параметры1);
    RecFunc(параметры3);
  }
}
Без рекурсии будет
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct Parameters {
  описание параметров
};
 
void NonRecFunc(Parameters параметры1){
  std::stack<Parameters> ParStack;
  ParStack.push(параметры1);
  while (!ParStack.empty()){
    параметры = ParStack.top();
    ParStack.pop();
    DoSomething(параметры);
    if (условие) {
      параметры3 = g(параметры);
      ParStack.push(параметры3);
      параметры2 = f(параметры);
      ParStack.push(параметры2);
    }
  }
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.01.2011, 20:27     Рекурсивная функция
Еще ссылки по теме:

C++ Рекурсивная функция
Рекурсивная функция C++
Рекурсивная функция C++

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

Или воспользуйтесь поиском по форуму:
BAIZOR
0 / 0 / 0
Регистрация: 30.10.2010
Сообщений: 68
06.01.2011, 20:27  [ТС]     Рекурсивная функция #8
Беда....
Переписал под вечный цикл(без вызова рекурсии)
Все равно где то есть утечка в памяти,но я удаляю все динамические объекты которые создаю,и даже использую указатели...
Пытаюсь по максимуму оптимизировать выделение памяти но с каждой итераций где то протекает =\

Код без рекурсии:
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
int* Lab1_All_Perebor(int **A,int *n,int *indexes,int *bestN,int *bestIndexes,int *bestShtraf,int *bestPrice,int *price,bool *metod)
{
    for(;;)
    {
        //Sleep(10);
        p++;
        SendMessage(GhWnd,WM_COLORED,(WPARAM)*n,(LPARAM)indexes);
        if(*n>N)
        {
            if(*bestN>0)
            {
                int *timebuf;timebuf=new int[*bestN+1];
                timebuf[0]=*bestN;
                for(int q=1;q<*bestN+1;q++)
                {
                    timebuf[q]=bestIndexes[q-1];
                }
                return timebuf;//////////////////////////////////////////EXIT
            }
            else
            {
                int *timebuf;timebuf=new int[1];timebuf[0]=0;
                return timebuf;//////////////////////////////////////////EXIT
            }
        }
        int *buf;
        buf=new int[M-1];
        for(int q=0;q<M-1;q++)
        {
            buf[q]=0;
        }
        int thisShtraf=0;
        *price=0;
        for(int Q=0;Q<*n;Q++)
        {
            for(int q=0;q<M-1;q++)
            {
                buf[q]+=A[indexes[Q]][q];
            }
            *price+=A[indexes[Q]][M-1];
        }
        bool flag=true;
        for(int q=0;q<M-1;q++)
        {
            if(buf[q]>1){thisShtraf++;}
            if(buf[q]==0){flag=false;}
        }
        delete buf;
 
        if(*metod)
        {
            if(flag&&thisShtraf<*bestShtraf)
            {
                flag=false;
                *bestShtraf=thisShtraf;
                *bestN=*n;
                //delete bestIndexes;
                bestIndexes=new int[*n];
                *bestPrice=*price;
                for(int q=0;q<*n;q++)
                {
                    bestIndexes[q]=indexes[q];
                }
            }
        }
        else
        {
            if(flag&&*price<*bestPrice)
            {
                flag=false;
                *bestShtraf=thisShtraf;
                *bestN=*n;
                //delete bestIndexes;
                bestIndexes=new int[*n];
                *bestPrice=*price;
                for(int q=0;q<*n;q++)
                {
                    bestIndexes[q]=indexes[q];
                }
            }
        }
    
 
        /////////////////////////////////////////////////////SHOW
 
        ////system("cls");
        ////wcout<<L"\n\n   Это "<<p<<L" проход функции\n\n\n\n";
        //for(int q=0;q<n;q++)
        //{
        //  //cout<<"                  ";
        //  for(int w=0;w<M;w++)
        //  {
        //      //cout<<A[indexes[q]][w]<<"  ";
        //  }
        //  //cout<<"          "<<indexes[q]<<endl;
        //}
        ////wcout<<"\n\n\n       buf        ";for(int q=0;q<M;q++){cout<<buf[q]<<"  ";}cout<<"\n\n\n";
        //if(bestN>0)
        //{
        //  //wcout<<L"                              Лучший:\n";
        //  for(int q=0;q<bestN;q++)
        //  {
        //      //cout<<"                  ";
        //      for(int w=0;w<M;w++)
        //      {
        //          //cout<<A[bestIndexes[q]][w]<<"  ";
        //      }
        //      //cout<<"          "<<bestIndexes[q]<<endl;
        //  }
        //}
        ////getch();///////////////////////WAIT BUTTON
 
        ///////////////////////////////////////////////////////////
 
        if(indexes[*n-1]<N-1)
        {
            indexes[*n-1]++;
            continue;
            //return Lab1_All_Perebor(A,n,indexes,bestN,bestIndexes,bestShtraf,bestPrice,price,metod);////////RECYRTION
        }
        else
        {
            if(*n==1)
            {
                if(indexes[0]<N-1)
                {
                    indexes[0]++;
                }
                else
                {
                    *n+=1;
                    //delete indexes;
                    indexes=new int[*n];
                    for(int q=0;q<*n;q++)
                    {
                        indexes[q]=q;
                    }
                }
                continue;
                //return Lab1_All_Perebor(A,n,indexes,bestN,bestIndexes,bestShtraf,bestPrice,price,metod);////////RECYRTION
            }
 
            for(int q=*n-1;q>=0;q--)
            {
                if(indexes[q]<indexes[q+1]-1){indexes[q]++;for(int w=q+1;w<*n;w++){indexes[w]=indexes[w-1]+1;}
                    return Lab1_All_Perebor(A,n,indexes,bestN,bestIndexes,bestShtraf,bestPrice,price,metod);////////RECYRTION
                }
                if(q==0)
                {
                    *n+=1;
                    //delete indexes;
                    indexes=new int[*n];
                    for(int q=0;q<*n;q++)
                    {
                        indexes[q]=q;
                    }
                    continue;
                    //return Lab1_All_Perebor(A,n,indexes,bestN,bestIndexes,bestShtraf,bestPrice,price,metod);////////RECYRTION
                }
            }
        
            *n+=1;
            //delete indexes;
            indexes=new int[*n];
            for(int q=0;q<*n;q++)
            {
                indexes[q]=q;
            }
        
            ////
            continue;
            //return Lab1_All_Perebor(A,n,indexes,bestN,bestIndexes,bestShtraf,bestPrice,price,metod);////////RECYRTION
        }
    }
}
Добавлено через 5 часов 9 минут
Ошибку устранил!!!
Нашел лишний вызов рекурсии.
Всем спасибо огромное!)
Особенно KEKCoGEN за идею оптимизировать алгоритм!)))
Yandex
Объявления
06.01.2011, 20:27     Рекурсивная функция
Ответ Создать тему
Опции темы

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