Почему моя функция 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 в основном достигнута, поэтому я уверен, что базовый случай в моей функции достигнут.

Здесь работает функция:

#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 (Stack Overflow distress Signal), однако в следующий раз я обязательно перейду через отладчик, прежде чем задавать вопрос.

Answer 1

Вы рекурсии в то время цикла:

в то время как (условие) рекурсивный вызов в то время как (условие) рекурсивный вызов . . .

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

если (условие) рекурсивного вызова рекурсивного вызова рекурсивного вызова

вы видите? Избавьтесь от этого и замените его инструкцией «if».

Answer 2

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

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

Answer 3

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

Answer 4

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

Answer 5

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

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

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 8

Вы неправильно понимаете точку рекурсивной функции. Если какое-либо условие истинно, вы возвращаете результат вызова рекурсивной функции, иначе вы возвращаете другое значение. Например, здесь является рекурсивное определение функции факториала (например 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, умноженное на 1 менее n.

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

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

Удачи вам!