Линейный алгоритм поиска с рекурсивным вызовом?

Question

Я делаю несколько упражнений, чтобы получить рекурсивные вещи. Один из них - я пытаюсь переписать линейный поиск с рекурсией. Вот оно:

int linearSearch(int a[], int n, int key) 
{ 
    if (n < 0) 
    { 
      return -1; 
    } 
    if(key == a[n-1]) 
    { 
      return n - 1; 
    } 
    linearSearch(a, n-1, key); // Line 1 
} 

код не был выполнен правильно, если он не имеет return заявление. Я не понимаю, почему нам нужно поставить оператор return в строке 1? Нужно ли нам в этом случае рекурсивно вызывать рекурсию только для уменьшения n на 1?

Answer 1

linearSearch(a, n-1, key); // Line 1 

Вы должны return значение из рекурсивного invokation:

return linearSearch(a, n-1, key); 

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

Базовые статьи, которые возвращают n-1 или -1 - просто возвращают его своему вызывающему абоненту, что является той же функцией! но не возвращая его оттуда, он никогда не достигнет первоначального вызывающего абонента.

Answer 2

Следующая строка может привести к сбою (или производят неожиданное значение) при п = 0:

if(key == a[n-1]) 

вы должны изменить ваш первый, если заявление:

if (n <= 0) 

Answer 3

Вы не можете вызвать функцию с некоторыми возвращаемый тип, не присваивая его переменной. В строке 1 оператор linearSearch(a, n-1, key); , так как функция имеет тип возврата, поэтому утверждение недействительно. Вы должны написать return linearSearch(a, n-1, key); в строке 1.

Answer 4

Imagina эта функция (возможно, это помогает)

int fortytwo(void) { 
    if (0) return 0; /* make the compiler less sad */ 
    42; 
}