ошибка рекурсивной функции: «переполнение стека» - PullRequest
Новая
       5

ошибка рекурсивной функции: «переполнение стека»

0 голосов
/ 12 июля 2011

Я написал эту функцию, которая должна находить наименьшее положительное целое число, которое делится на каждое число от 1 до 20. Я получаю «ошибку переполнения стека», хотя, когда я проверяю числа от 1 до 10, она работает просто отлично.вот мой код: 

#include<iostream>
#include<cstdlib>

using namespace std;

// function prototype
int smallPos(int k, int m,int n);

int main(){
    printf("the smallest positive number that is divisible by 1 through 20 is %d ", smallPos(1,1,13));

}

int smallPos(int k, int n, int m){
    int div=0;
    for(int i = n;i<=m;i++) {
        if (k%i==0) 
            div++;
    } 
    if (div==m) {
        return k;
    } else {
        k+=1;
        smallPos(k,n,m);
    }   
}

Почему это происходит?Число не должно быть таким большим в любом случае.Спасибо!

Ответы [ 2 ]

5 голосов
/ 12 июля 2011

Конечное условие (div == m) никогда не будет верным. Чтобы div стало равным m, число k должно делиться на все чисел в диапазоне [n,m).

Редактировать : Я перечитал текст в вызове printf(), чтобы понять, что делает функция. Вы ищете первое число, делимое на все числа в диапазоне. Если мои расчеты верны, это число должно быть произведением всех уникальных простых множителей чисел в диапазоне. Для диапазона [1,13] (согласно вызову функции, а не текста) это число должно быть: 

30030 = 1 * 2 * 3 * 5 * 7 * 9 * 11 * 13

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

Редактировать : вот итерационная версия, которая, кажется, работает. 

int smallPos ( int n, int m )
{
    int k = 0;
    while ( ++k )
    {
        int count = 0;
        for (int i = n; i<=m; i++)
        {
            if (k%i==0) {
                ++count;
            }
        }
        if (count == (m-n+1)) {
            return k;
        }
    }
    return k;
}

Действительно, результат для smallPos(1,10), результат - 2520. Кажется, моя предыдущая оценка была нижней границей, а не фиксированным результатом.

1 голос
/ 12 июля 2011

Ваша smallPos функция имеет неопределенное поведение, так как она не возвращает значение во всех путях выполнения.Вы можете сказать return smallPos(k,n,m); в последней части (или просто return smallPos(k + 1, n, m); за один раз).

...