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

Переполнение стэка при рекурсии - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 5.00
Dobroe_Zlo
0 / 0 / 0
Регистрация: 14.06.2011
Сообщений: 7
14.06.2011, 18:10     Переполнение стэка при рекурсии #1
вот код:
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
#include <iostream>
 using namespace std;
 void Vvod (int *A, int n)
 {
 for (int i=0;i<n;i++) 
 {
         cin>>A[i];
 }
 }
  int Proizvedenie (int A[],int n)
  {
      if(A[n]>0)
      {
        return Proizvedenie (A,n-1)*A[n];
      }
      else 
          return Proizvedenie (A,n-1);
  }
        
 void Vivod (int *A, int n)
 {
         int i;
 for ( i=0; i < n;i++)
 cout<<A[i];
 cout<<"\n"<<Proizvedenie(A,n);
 }
void main() 
 {
 int n;
 cin>>n;
 int *A=new int[n];
 Vvod(A,n);
 Vivod(A,n);
 cin.get();
 cin.get();
 }
компилятор выдает ошибку "Рекурсивная функция Proizvedenie вызовет переполнение стэка" и из-за этого программа не высчитывает произведение элементво в массиве.
что мне сделать чтоб программа нормально работала?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.06.2011, 18:10     Переполнение стэка при рекурсии
Посмотрите здесь:

C++ елка при помощи рекурсии
C++ переполнение при считывание из файла
Размер стэка и кучи C++
C++ Переполнение строки при считывании из файла
Переполнение при расчете функции C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
14.06.2011, 18:17     Переполнение стэка при рекурсии #2
Dobroe_Zlo, нету базы рекурсии, которая бы остановила последовательность рекурсивных вызовов (читай: рекурсия у тебя бесконечная)
Dobroe_Zlo
0 / 0 / 0
Регистрация: 14.06.2011
Сообщений: 7
14.06.2011, 18:19  [ТС]     Переполнение стэка при рекурсии #3
Цитата Сообщение от Nameless One Посмотреть сообщение
Dobroe_Zlo, нету базы рекурсии, которая бы остановила последовательность рекурсивных вызовов (читай: рекурсия у тебя бесконечная)
да, я в курсе, но немогу правильно подобрать условия окнчания, поэтому и обратился за помощью к вам
grizlik78
Эксперт С++
 Аватар для grizlik78
1884 / 1416 / 102
Регистрация: 29.05.2011
Сообщений: 2,961
14.06.2011, 18:21     Переполнение стэка при рекурсии #4
Да, со строкой номер 17 явно не угадал.
Условие правильное, неправильный возврат.
А вообще, рекурсия — зло. Надеюсь авторы заданий на рекурсию это объясняют

Добавлено через 58 секунд
Уточню: в нефункциональных языках.
Dobroe_Zlo
0 / 0 / 0
Регистрация: 14.06.2011
Сообщений: 7
14.06.2011, 18:22  [ТС]     Переполнение стэка при рекурсии #5
grizlik78,
вроде объясняют, но чето с этой задачей я уже почти часа мучаюсь
grizlik78
Эксперт С++
 Аватар для grizlik78
1884 / 1416 / 102
Регистрация: 29.05.2011
Сообщений: 2,961
14.06.2011, 18:26     Переполнение стэка при рекурсии #6
У тебя оба ретурна используют рекурсивный вызов. А должен быть хотя бы один вариант ответа без рекурсии.

Добавлено через 1 минуту
Поставим вопрос так:
Чему должно равняться произведение 0 сомножителей, чтобы при умножении его на число получилось это самое число (т.е. произведение из одного сомножителя) ?
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
14.06.2011, 18:27     Переполнение стэка при рекурсии #7
Цитата Сообщение от grizlik78 Посмотреть сообщение
А вообще, рекурсия — зло.
Популярные компиляторы С/С++ (т.е. gcc и cl.exe) умеют оптимизировать хвостовую рекурсию, так что ее вполне-таки можно использовать (с умом, конечно). Да и обработку рекурсивных типов данных (деревья и т.д.) с помощью циклов реализовывать проблематично.
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
14.06.2011, 18:28     Переполнение стэка при рекурсии #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
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
 
int product(size_t, ...);
 
int main()
{
 
    printf("Product of 3 5 8 3 2 is %d\n", product(5, 3, 6, 8, 3, 2));
    
    exit(0);
}
 
int calc_product(size_t n, va_list ap)
{
    int value;
 
    if(!n)
    return 1;
 
    value = va_arg(ap, int);
 
    return value * calc_product(n - 1, ap);
}
 
int product(size_t n, ...)
{
    int result;
    
    va_list ap;
    va_start(ap, n);
    result = calc_product(n, ap);
    va_end(ap);
 
    return result;
}
Здесь рекурсивная функция - calc_product
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
14.06.2011, 18:32     Переполнение стэка при рекурсии #9
Ну и вариант с массивом:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
 
int product(size_t, int*);
 
int main()
{
    int arr[5] = {1, 2, 3, 4, 5};
        
    printf("5! = %d\n", product(5, arr));
    
    exit(0);
}
 
int product(size_t n, int* arr)
{
    if(!n)
    return 1;       /* Тривиальный случай */
 
    return *arr * product(n - 1, arr + 1);
}
Ну и наконец вариант с хвостовой рекурсией:
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
#include <stdio.h>
#include <stdlib.h>
 
int product(size_t, int*);
 
int main()
{
    int arr[5] = {1, 2, 3, 4, 5};
        
    printf("5! = %d\n", product(5, arr));
    
    exit(0);
}
 
static int product1(size_t n, int* arr, int acc)
{
    if(!n)
    return acc;
    return product1(n - 1, arr + 1, acc * *arr);
}
 
int product(size_t n, int* arr)
{
    return product1(n, arr, 1);
}
grizlik78
Эксперт С++
 Аватар для grizlik78
1884 / 1416 / 102
Регистрация: 29.05.2011
Сообщений: 2,961
14.06.2011, 18:45     Переполнение стэка при рекурсии #10
calc_product выглядит интересно, до тех пор пока не попробовать реализовать то же самое для double, а потом вызвать это как-нибудь так: product(5.5, 3, 6)

Ну и в обоих случаях нет никакой веской причины для рекурсии. А гадать потом, преобразует компилятор рекурсию в цикл, или нет...
Я понимаю там Haskell какой... Ладно, не будем холиварить, пожалуй
Dobroe_Zlo
0 / 0 / 0
Регистрация: 14.06.2011
Сообщений: 7
14.06.2011, 18:56  [ТС]     Переполнение стэка при рекурсии #11
чёто у меня всеравно не получается
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
14.06.2011, 19:00     Переполнение стэка при рекурсии #12
Цитата Сообщение от grizlik78 Посмотреть сообщение
calc_product выглядит интересно, до тех пор пока не попробовать реализовать то же самое для double, а потом вызвать это как-нибудь так: product(5.5, 3, 6)
В смысле? Для double все реализуется так же (единственный обязательный аргумент функции - это число необязательных аргументов, которые мы передаем):
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
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
 
double product(size_t, ...);
 
int main()
{
 
    printf("Product of 3.1 6.3 8.8 3.2 2.1 is %.4f\n", product(5, 3.1, 6.3, 8.8, 3.2, 2.1));
    
    exit(0);
}
 
double calc_product(size_t n, va_list ap)
{
    double value;
 
    if(!n)
        return 1;
 
    value = va_arg(ap, double);
 
    return value * calc_product(n - 1, ap);
}
 
double product(size_t n, ...)
{
    double result;
    
    va_list ap;
    va_start(ap, n);
    result = calc_product(n, ap);
    va_end(ap);
 
    return result;
}

Не по теме:

Цитата Сообщение от grizlik78 Посмотреть сообщение
Я понимаю там Haskell какой... Ладно, не будем холиварить, пожалуй
В Haskell'е (да и в других функциональных языках) не так уж и часто возникает необходимость описывать алгоритм решения задачи с помощью явной рекурсии - часто его можно выразить через функции высшего порядка - свертки (foldl, foldr), отображения (map, fmap), фильтрации (filter) и т.д. Для свертки и отображения так вообще классы типов сделали, что позволяет их "распространить" на произвольный рекурсивный тип данных



Dobroe_Zlo, а поконкретнее? Какой компилятор? Какие ошибки?
Dobroe_Zlo
0 / 0 / 0
Регистрация: 14.06.2011
Сообщений: 7
14.06.2011, 19:01  [ТС]     Переполнение стэка при рекурсии #13
всем большое спасибо, особенно Nameless One,
все оказалось немного проще, готовый код выглядит так:
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
#include <iostream>
 using namespace std;
 void Vvod (int *A, int n)
 {
 for (int i=0;i<n;i++) 
 {
         cin>>A[i];
 }
 }
  int Proizvedenie (int *A,int n)
  {
      if(!n)
      {
        return 1;
      }
      else 
          return *A*Proizvedenie (A+1,n-1);
  }
        
 void Vivod (int *A, int n)
 {
         int i;
 for ( i=0; i < n;i++)
 cout<<A[i];
 cout<<"\n"<<Proizvedenie(A,n);
 }
void main() 
 {
 int n;
 cin>>n;
 int *A=new int[n];
 Vvod(A,n);
 Vivod(A,n);
 cin.get();
 cin.get();
 }
у меня в формальных переменных был просто инициализирован массив А, а в самой рекурсии был указатель на этот массив, вот из-за такой мелочи я парился почти 40 мин.
no0ker
100 / 87 / 4
Регистрация: 17.12.2010
Сообщений: 416
14.06.2011, 19:04     Переполнение стэка при рекурсии #14
наверное глупый вопрос, но все таки. а зачем объявлять функцию static?
C++
1
static int product1(size_t n, int* arr, int acc)
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
14.06.2011, 19:07     Переполнение стэка при рекурсии #15
no0ker, чтобы она была видна только в текущей единице трансляции (т.к. она является вспомогательной для функции product и отдельно ее использование не планировалось)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.06.2011, 19:53     Переполнение стэка при рекурсии
Еще ссылки по теме:

C++ Переполнение при вводе int
C++ Как происходит переполнение при делении
C++ Переполнение буфера при поиске WNDDIR

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

Или воспользуйтесь поиском по форуму:
grizlik78
14.06.2011, 19:53     Переполнение стэка при рекурсии
  #16

Не по теме:

Цитата Сообщение от Nameless One Посмотреть сообщение
В смысле? Для double все реализуется так же (единственный обязательный аргумент функции - это число необязательных аргументов, которые мы передаем)
Первый аргумент я, конечно, потерял, должно было быть product(3, 5.5, 3, 6), но я имел в виду здесь не проблему рекурсии, а проблему переменного количества аргументов, а именно отсутствие проверки типов.

Yandex
Объявления
14.06.2011, 19:53     Переполнение стэка при рекурсии
Ответ Создать тему
Опции темы

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