Почему моя функция recursiveMinimum не работает?

Question

#include <iostream>
using namespace std;

int recursiveMinimum(int [], int n);

int main () 
{
    int theArray[3] = {1,2,3};

    cout << recursiveMinimum(theArray, 0);
    cout << endl;
    return 0;
}


// pass in array and 0 to indicate first element
// returns smallest number in an array
int recursiveMinimum (int anArray[], int n) // nth element is smallest element in anArray
{
    while (anArray[n+1] != NULL)
    {
        int smallest = n;
        if (anArray[n+1] <= anArray[n])
            smallest = n + 1;
        //if last element has not been reached
        return recursiveMinimum(anArray, smallest);
    }
}

Моя функция завершается, но ничего не возвращает. Я пытался установить базовый случай, когда достигается за пределами массива. Строка возврата 0 в main достигнута, поэтому я уверен, что базовый случай в моей функции достигнут.

Вот рабочая функция:

#include <iostream>
using namespace std;

 int recursiveMinimum(int a[],int min,int index,int size);

int main()
{
    int a[6] = {8, 2, 55, 3, 11, 9};
    cout << recursiveMinimum(a,a[0],1,6) << endl;
    return 0;
}

// pass in the array, the first element, 
// 1 to indicate 2nd element, and the number of elements
int recursiveMinimum(int a[],int min,int i,int size)
{
    if(i == size )
       return min;

    else if(i < size)
    {
       if(a[i] < min)    
          recursiveMinimum(a,a[i], i + 1, size);
       else 
          recursiveMinimum(a,min, i + 1, size);      
    }

}

Спасибо всем, кто помог. Из-за нехватки времени я разослал SOS (переполнение стека сигнал бедствия сигнал), однако в следующий раз я обязательно перейду к отладчику, прежде чем задать вопрос.

Answer 1

Вы прошли через это в отладчике? Это должно стать довольно очевидным, когда вы это сделаете.

Answer 2

Вы возвращаетесь в цикле while:

пока (условие) рекурсивный вызов пока (условие) рекурсивный вызов , , .

Вместо этого вы, вероятно, думали:

if (условие) рекурсивный вызов рекурсивный вызов рекурсивный вызов

понимаешь? Избавьтесь от while и замените его оператором if.

Answer 3

У вас должен быть конечный случай с рекурсивной функцией.

В данный момент ваша функция всегда возвращает себя. Это будет повторяться до тех пор, пока не закончится стек. Вам нужно иметь проверку, которая говорит «Я сделал», которая будет возвращать значение, а не результат вызова другой функции.

Answer 4

Вы неправильно понимаете смысл рекурсивной функции. Если определенное условие истинно, вы возвращаете результат вызова рекурсивной функции, в противном случае вы возвращаете какое-то другое значение. Например, вот рекурсивное определение факториальной функции (например, 5!, или "5 факториал", равно 5*4*3*2*1, что равно 125):

int
factorial (int n)
{
  if (n == 1)
    return n;
  return (n * factorial (n - 1));
}

Как это работает:

• Если n равно 1, вернуть 1, поскольку 1! равно 1.

• В противном случае вернуть n, умноженное на единицу меньше n.

Например, если n равно 5, возвращаемое значение является результатом выражения 5 * factorial (5 - 1), которое совпадает с 5 * factorial (4). Конечно, то же самое происходит снова, поскольку это рекурсивная функция, а 4 - это не 1. Таким образом, вы получите 5 * factorial (4), что соответствует 5 * (4 * factorial (4 - 1)) или 5 * (4 * factorial (3)).

Теперь вы сможете увидеть схему и узнать, как работает факториальная функция. Ваша функция recursiveMinimum должна придерживаться той же общей идеи - если что-то истинно (или не истинно), вернуть результат вызова функции (возможно, с некоторыми дополнительными вещами, такими как значение n внутри функции факториала, необходимо умножить результатом факториальной функции), иначе возвращает определенное значение и код функции, чтобы обработать его соответствующим образом. Другими словами, вам нужно «конечное» условие выхода, такое как условие n == 1 в функции факториала выше.

Удачи!

Answer 5

 int recursiveMinimum(int a[],int min,int index,int size)
{
    if(index == size )
       return min;

    else if(i < size)
    {
       if(a[i] < min)    
          recursiveMinimum(a,a[i],++index,size);
       else 
          recursiveMinimum(a,min,++index,size);      
    } 

}

int main()
{
    int a[] = {1,2,3,0,-4};
    int min = recursiveMinimum(a,a[0],1,5));
    return 0;
}

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

Я думаю, что поиск минимума более эффективен, легок и прост, используя итерацию, а не рекурсию.

Answer 6

вместо

int recursiveMinimum(int array[], int n);

Я думаю, что recursiveMinimum должно быть определено как

int recursiveMinimum(int array[], int index, int length);

с намерением, чтобы recursiveMinimum вернул минимальное значение в array между индексами index и length (т.е. min array[i], где i в [index, length)). Конечно, вы хотите определить это рекурсивно. Тогда я хотел бы отметить, что минимальное значение в array между индексами index и length равно

min(array[index], recursiveMinimum(array, index + 1, length));

Конечно, существуют граничные случаи (например, когда index = length - 1). В этом случае вы просто вернете array[index] как минимум.

Надеюсь, это поможет. Дайте мне знать, если это не имеет смысла.

Answer 7

Вы никогда не нарушите свою рекурсию. На самом деле мне интересно, что это компилируется, так как ваша функция даже не имеет определенного возвращаемого значения в случае, если оно достигает конца. Также использование while кажется ненужным, так как выполнение функции в любом случае останавливается после возврата.

Answer 8

Потому что ваш цикл while никогда не заканчивается. Почему вы уверены, что anArray[n+1] будет когда-нибудь NULL?