Как компилятор C работает с локальной переменной в стеке во время рекурсии?

Question

Я пишу простую программу бинарного поиска и сталкиваюсь с проблемой, см. Мои три путаницы ниже:

• Если я выберу icc -g main.c или icc -O0 main.c, код вернет неправильный ответ, но если я использую icc -O2 main.c, у меня может быть правильный ответ.

• Когда код mid = (beg + end) / 2; будет определен до if(beg <= end) {, ответ будет правильным независимо от того, какой флаг я использую для его компиляции.

• Я думаю, что проблема заключается в локальной переменной mid в стеке во время рекурсии.

Помоги мне, спасибо!

#include <stdio.h>
#define MAX 6
int a[MAX] = {1,2,3,4,5,6};
int improved_binary_search(int key, int beg, int end) {
    int mid, temp;
    //mid = (beg + end) / 2;
    if(beg <= end) {
             mid = (beg + end ) /2;
             if(a[mid] == key)
                     return mid;
             if(a[mid] < key)
                     return improved_binary_search(key, mid + 1, end);
              if(a[mid] > key)
                      return improved_binary_search(key, beg, mid - 1);
              //printf("test is %d\n", mid);
      }
      if(mid == 0)
              return 0;
      if(mid == MAX - 1)
              return MAX - 1;
      if(a[mid] < key)
              return a[mid+1] - key < key - a[mid] ? mid+1 : mid;
      if(a[mid] > key)
              return a[mid] - key < key - a[mid-1] ? mid : mid-1;
      return -1;
  }

int main(void)
{
     printf("%d\n", improved_binary_search(100, 0, MAX - 1));
     return 0;
}

Answer 1

Вы только что объявили mid, но не инициализировали его, может случиться так, что если первое условие if (if(beg <= end)) не выполнено, тогда значение mid равно Indeterminate .

Это приведет к неопределенному поведению . Поведение, которое вы видите, происходит из-за этого UB, а не из-за конфигураций компилятора.

Вы всегда должны инициализировать свои переменные значимыми значениями.

Answer 2

Одной из проблем является то, что вы не инициализируете mid, если beg <= end.Затем (потенциально неинициализированная) переменная используется во второй половине improved_binary_search().Это неопределенное поведение.

Чтобы исправить, всегда инициализируйте mid.