Почему мы должны использовать оператор return при использовании рекурсивного вызова?

Question

В приведенной ниже функции двоичного поиска, возвращающей значение целочисленного типа, почему мы должны использовать возвращаемое значение в обоих инструкциях else if при рекурсивном вызове? Код не будет работать, если я использую рекурсивный вызов вместо того, чтобы использовать его взамен.

int binarysearch(int l,int h,int key)
{
  int mid;
  mid=(l+h)/2;
  if(l<=h)                             
  {
    if(key==a[mid])
      return mid;
    else if(key>a[mid])
      return(binarysearch(mid+1,h,key));
    else if(key<a[mid])
      return(binarysearch(l,mid-1,key));
  }
  else
    return -1;
}

Answer 1

Хотя возвращаемое значение имеет тип int, функция должна возвращать значение. Каждое место, куда он возвращается, должно возвращать значение. Когда рекурсивный вызов, сделанный текущим вызовом функции, возвращается, он дает вам ответ; вы должны вернуть этот ответ в контекст вызова - либо на следующий уровень вверх по цепочке рекурсии, либо в исходный вызывающий объект.

Если вы не возвращаете значение, вы вызываете неопределенное поведение , которое это плохо! ™

Answer 2

Если прототип вашей функции определяет, что ее тип возвращаемого значения является недействительными данными, то в теле этой функции ДОЛЖНО быть возвращено значение типа, указанного в прототипе. Обратите внимание, что в прототипе вашей функции явно указано, что должно быть возвращено значение типа "int":

int binarysearch(int l, int h, int key);

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

Если вы не хотите использовать return, ваша функция должна иметь следующий прототип:

void binarysearch(int l, int h, int key, int *mid);

В этом случае вы должны использовать указатель для извлечения значения "mid" из внутреннего контекста этой функции.

Answer 3

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

extern int a[];
int binarysearch(int l,int h,int key)
{
  int mid;
  mid=(l+h)/2;
  if(l<=h) {
    if(key>a[mid]) {
      mid = binarysearch(mid+1,h,key);
    } else if(key<a[mid]) {
      mid = binarysearch(l,mid-1,key);
    }
  } else {
    mid = -1;
  }
  return mid;
}

Ваша первоначальная функция вызвала для меня диагностику компилятора c:

bb. c: 17: 1: предупреждение: элемент управления может достигнуть конца недействительной функции [-Wreturn-type]}

Что выглядит как ложное предупреждение компилятора, поскольку он видит, что конструкция:

if (a == b) {
    return ...;
} else if (a < b) {
    return ...;
} else if (a > b) {
    return ...;
}

имеет некоторые другие возможности. Я добавил:

return -42;

и это, казалось, удовлетворило его.