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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
BAIZOR
0 / 0 / 0
Регистрация: 30.10.2010
Сообщений: 68
#1

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

06.01.2011, 06:54. Просмотров 556. Ответов 7
Метки нет (Все метки)

Как быть?

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

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

Рекурсивная функция - C++
Скласти програму з використанням рекурсивної функції, в якій обчислити суму 12 членів рекурентної послідовності : X0=1;X1=1;Xk=0,7Xk-1+...

Рекурсивная функция - C++
ПРивет всем! ребят помогите решать вот такую задачку: Используя команды write(x) лишь при х=0,1,…9 написать рекурсивную процедуру вывода...

Рекурсивная функция - C++
Вычислить элементы ряда с помощью рекурсивной функции. Порядок вычисления элементов ряда: a(1)=1, a(n)=5*(2n-1)n-a(n-1), n>0 ...

Рекурсивная функция C++ - C++
Сосчитать f(y)=3y+5, yk - входное данное.

Рекурсивная функция - C++
Как мне оформить в рекурсивную функцию? Напишите код пожалуйста, буду благодарен)) #include <iostream> #include <conio.h> using...

Рекурсивная функция - C++
Здравствуйте, появилась проблемма с написание программы которая использует рекурсивную функцию. Задание: Вот неочень удачная наброска...

7
KEKCoGEN
Эксперт Java
1934 / 1812 / 437
Регистрация: 28.12.2010
Сообщений: 7,266
06.01.2011, 07:00 #2
Впринципе можно увеличить стек, но наверняка можно оптимизировать алгоритм. Может приведете код рекурсии?
0
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
06.01.2011, 09:27 #3
BAIZOR, условие задачи напишите и код который Вы написали.
0
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 и сделать не рекурсию а вечный цикл используя проверку на выход из цыкла от рекурсии.
Останеться сделать только все переменные за этим цыклом.

Но мне интересно возможно ли сделать так что бы рекурсия вызывалась очень много раз ?
0
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. Не посмотрел, что это сишный форум. Но думаю идея понятна и на Паскале.
1
BAIZOR
0 / 0 / 0
Регистрация: 30.10.2010
Сообщений: 68
06.01.2011, 14:51  [ТС] #6
Размер матрицы NxM
n это кол-во строк для склеивания(суммирования)

dikanev,а вы бы не могли привести пример на Visual С++?
0
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);
    }
  }
}
1
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 за идею оптимизировать алгоритм!)))
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.01.2011, 20:27
Привет! Вот еще темы с ответами:

Рекурсивная функция - C++
...помогите пожалуйста сделать задачки... http://cs4734.vkontakte.ru/u26212689/96588963/x_20024bb4.jpg ...

Рекурсивная функция - C++
Здраствуйте, пытаюсь написать лабу для нахождения пути в лабиринте, выбрал волновой алгоритм Ли. Для начала хочу просто заполнить...

Рекурсивная функция - C++
С клавиатуры вводится массив из 20 элементов. Заменить все отрицательные элементы суммой чётных! int x,h; void input(int i){ ...

Рекурсивная функция - C++
Написать на языке С рекурсивную функцию вычисляющую количество полных расстановок скобок в произведении n чисел


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

Или воспользуйтесь поиском по форуму:
8
Yandex
Объявления
06.01.2011, 20:27
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru